What the course is about: What to do when traditional software engineering methods lead to a dead end.

• For example, you have a functional requirement for which you can find no known algorithm that will satisfy the requirement.
• Or, you find such an algorithm, but it requires more computing time than your application can accept.
• When the above are true, and a not-quite perfect solution is acceptable, then soft computing techniques can frequently be of great use.
• Problems that you previously would not consider solving by computer may become solvable once you understand how to apply these techniques.

Preliminaries:

You don't need any texts to get started!
 

None of the texts and web resources truly reflect the content or point of view of this course; use the texts primarily as sources of information, not as sources of direction.

Remember that our point of view is Software Engineering.

We are much more concerned with applications and practicalities than with theory or mathematics.  Where theory and mathematics have practical impact, we will address them.

Soft Computing:

• Traditional software development (based on guaranteed algorithms such as those that implement the Pythagorean theorem, and are based on Boolean logic) are not soft computing.
• May reject (at least in part) Boolean logic, replacing it with fuzzy logic, probabilistic answers, or other answers that are not completely definite.
• May produce "good enough" answers that may not be the best answers.
• May be based on a biologically-inspired model of computation such as neural networks or genetic algorithms.
• May be based on recent advances in mathematics, such as chaos theory (non-linear systems) or fractals.
• May use some results from "traditional" (symbolic) Artificial Intelligence (AI), such as heuristic search of semantic nets.

A (Homework) Problem (preparation for later projects) in "Naive Genetic Algorithms":

• We will address a problem to which we already know the solution, in order to get a feel for the GA approach, and to have a simple means for checking the results of our experimentation.  This is a preparation for a homework exercise (Project 1).
• Problem: Use "naive" GA techniques to find the closest or almost closest single jump from point A to point B in a linear three-dimensional space.  Ideally, we would parameterize the coordinates (x, y, z) of A and B so that they could be varied from one run to another.  Please use A = (1, 1, 1) and B = (11, 11, 11) for your initial work, and move on to other values after getting your code to "work" with these values.
• Do not wait to study any genetic algorithms in texts in order to begin this problem, although a reading of Part 2 of the GA FAQ may be helpful.  Use the "naive" GA material presented here (and repeated in class).  You can upgrade your approach later if you wish, but put development of this application (or applet) ahead of that study for now.
• Do experiment with your program to determine the effects of changing such parameters as your initial values, mutation rates or amounts, etc. (see below) to see how they affect the quality and convergence of your solution.
• Remember that our goal is to develop an ability to apply genetic algorithms; we already know the solution to this problem to which we are applying the GA!
• In this project, we pretend that, even though we know how to use the Pythagorean theorem to compute the distance between two point, we do not realize that this also gives us, in effect, the closest jump between the points.  We will try to compute that closed jump using a GA. However, we will use the Pythagorean theorem in two ways:
• We will use the Pythagorean theorem to compute the "miss distance" for our jump. The distance our jump takes us from point B is a measure of the quality or "cost" of our solution (jump). We seek to minimize cost (miss distance), which maximizes the quality of the solution. The "naive GA" will get us some approximate solution.
• We will use the Pythagorean theorem (or related geometry) to check the absolute quality of our solution. A perfect solution would be a jump of 10 units in each of the three directions (x, y, z). In terms of the variables defined below, D = (10, 10, 10) would be a perfect solution, taking us directly from A to B with a miss distance (cost) of zero. Point N (see below) and point B would be the same point.We can use this knowledge to experiment with how our choices (initial population, mutation rate, mutation amount, etc.) impact both the quality of the solutions produced by the GA and the speed with which it produces those solutions.

Applying the GA to this problem:

• Step 1: Identify Parameters:
• A and B (as above), the point we wish to jump from (A) and to (B).
• D or (dx, dy, dz), the jump, or the changes in the coordinates when moving from A to some new point (N).  In other word, Ax + dx = Nx, Ay + dy = Ny, Az + dz = Nz.  dx, dy, and dz are the "genes" for this project, and the set (vector [no, not a Java vector, a math vector]) (dx, dy, dz) is the "chromosome" for this project. (In vector terms, N = A + D). (Ideally, N would be equal to B, but often it will not. N will miss by some amount. We seek to minimize this miss distance using an evolutionary algorithm.)
• Acceptable cost: If the miss distance between N and B is less than 2, then we consider this an acceptable solution.  Obviously, you could parameterize the miss distance, so that you could experiment with the effect of varying the acceptable cost. It is better to do this after you get the naive GA working with a fixed miss distance, which will be challenge enough to start our with.
• Step 1a: Cost function (solution quality):
• The "cost function" is the distance from the new point "N" (guessed by the GA) to the target point B.  In other words,
• the square of the cost is =  (Nx - Bx)*(Nx - Bx) + (Ny -By)*(Ny -By) + (Nz -Bz)*(Nz -Bz)
• Step 2: Represent parameters.  I suggest representing them with doubles.
• Step 3: Create a population of chromosomes.  You will need several guesses (chromosomes) for the values of (dx, dy, dz).  How many?  That is part of the art and craft of GAs, but if you want an arbitrary figure, you could choose 24.
• Step 3: Selecting the values of the initial guesses.  How do you get initial values for the "genes"?  Some random generation approach is best, so you will probably want to use a random function from your programming environment.  How large a range of values should you allow?  Too big, and the algorithm will spend a lot of iterations on enormous jumps that can't possibly be right.  Too small, and the algorithm can't ever hit the target!  We already know that the ideal solution is dx =dy=dz=10 for the values of A and B given above. I suggest that the initial range be something like -20 to + 20, pretending that we don't know where point B is relative to point A.  Feel free to experiment!
• Step 4: Evaluate cost (initial).  For each chromosome, find the new point (N) that it creates by adding that chromosome to A.  That is, Nx = Ax + dx, Ny = Ay + dy, Nz = Az + dz.  Then apply the "cost function" from Step 1a to find the cost for each chromosome.  Sort the population in order of increasing cost.
• Step 4a: Evaluate cost (loop).  Same as step 4, but note that you already have the costs for the un mutated surviving parent chromosomes, so in iterations after the first you need to compute the costs only for the offspring and the mutated parents (if any).  Sort the population in order of increasing cost.
• Step 5: Test convergence.  If one or more chromosomes have a cost less than the acceptable cost, the lowest cost (smallest miss distance) chromosome of this set is selected as the solution, and the algorithm has finished.
• Step 6: Selection.  Keep only the best half of your chromosomes; delete the others.  If you started with 24, you will now have 12.  These are the parents for the next generation.  (Important note: there is evidence that this is not always the best selection algorithm, but it is simple, and is the basis for the other good algorithms.)
• Step 7: Pairing.  Pair the remaining chromosomes (parents) via any means.  For example, pair the best (lowest cost) chromosome with the next best, and so on down the list.  Or, pair the best with the worst, or pair them at random, or ....
• Step 8: Mating.  For each pair, select a crossover point.  For these short (length = 3) chromosomes, the crossover point will be between dx and dy, or between dy and dz.  As an example, lets assume that the crossover point is between dx and dy, and that the parents are named p1 and p2.  p1 looks like this: (dxp1, dyp1, dzp1), and p2 looks like this: (dxp2, dyp2, dzp2). Create the next generation by combining genes from one parent on one side of the crossover point with genes from the other parent from the other side of the crossover parent. With a crossover point between dx and dy, the two offspring chromosomes look like this: (dxp1, dyp2, dyp2) and (dxp2, dyp1, dzp1). Note that, in this version of an EA, we are keeping the best parents from the previous generation. The genes that the "offspring" get from their "parents" are actually copies of their parents' genes, because the parents still have their original genes!
• (Note) We began with, for example, 24 parents.  We eliminated 12 by selecting only the 12 "best" to survive into the next generation.  We have now created 12 new offspring (2 for each pair of parents), so we now have a population of 24 again, since we are keeping the 12 best parents into the next generation, and adding 12 new offspring.
• Step 9: Mutate.  (Without this step, there isn't much hope of eventual success!)  Using a random number generator, pick three or four (or some number determined at random, but neither too many nor too few) genes at random from the genes of the 23 highest cost chromosomes.  (In other words, don't mutate the lowest cost chromosome.) Change these genes by some small random amount.  How much?  This another good item to make into an input parameter.  If you wish to start out simple, for this problem, mutate by adding +1 or -1 to the selected "genes", and make the choice of the "+" or "-" sign random.
• Loop back to Step 4a.

  One more note: In EAs (including GAs), the computational "Achilles heel" of the algorithm is frequently the computation of the cost or quality function. For this simple problem, it shouldn't be too bad, but in a lot of more realistic applications it is a major issue.

Yet another note on biologically-inspired models of computation: These models (such as EAs/GAs and neural nets) do not exactly match what really happens in biology. Biology has been used to inspire new approaches to computational problem solving, but the computational models do not truly emulate biological processes.

PEM