Reviews - What do customers think about Why Things Are: How Complexity Theory Answers Lifes Toughest Questions?
Genetic Algorithms - Convergence - Assisted by reduction through observed rules Aug 28, 2007
1. Genetic programs involve large numbers of separate computer programs or rules, each of which is random in its ability to solve a given program.
2. The programs or rules that are the most successful in one generation are kept, mated with each other and occasionally mutated, reproduced, and put back into the fray to once again test their ability to solve the problem.
3. After time and sometimes thousands of generations that remain rules or programs are highly effective at solve the give set of problems.
4. For genetic algorithms to work, you need to be able to succinctly tell the computer the current state, which can consist of both the internal sate that acts as a form of status and the current values for all inputs, called the machine receptor. The state and receptor information is encoded in a string of digits. The values in the string are inputs to the genetic algorithm. A. Start by defining and listing the states in which the system can exist. B. Define the environmental input variables that need to available to the system. The system can only solve programs if the needed data is available to it. C. Define the range of possible values for each of the environmental inputs. D. Map the states and environmental inputs into the string.
5. Consider tic-tac-toe, the states are (won-me) or (won-you). String values are B,O,X and (M=my turn and Y=Your turn. The grid holds cells from 0 to 8 and a end cell for mine or your turn. The Input string BBBBBBBBBM could have one or more transition inputs, such as BBBBXBBBBY or XBBBXBBBBY. GA use wild card rules to solve the problem of multiple transitions. These rules act as defaults, being available for triggering when no more specific rule seems appropriate. ****B*****Y rule matches on any board configuration that has a blank in the center. "There are 57 possible 'boards' that X has to be able to respond to, and only 38 possible boards that O will ever encounter " says Paul Thiessen. Thiessen discovered it is an advantage to have the first move, 6-10 generation convergence. GA complexity can be reduced by intelligently limiting genes by observed rules. GA are not total random. Complexity is reduced by intelligently apply observed rules and rewards.
6. Solutions are the result of converging to a global min on a gradient 3d map. Mutation perturbs the system helping the GA from getting caught in a local minimum. Over time bad rules are weeded out and the program is left with the good rules. The number of rules to randomly generate depends on the number of possible input strings. The larger the number of input strings, the more rules are needed to cover a somewhat percentage of the possible values. A relatively few number of rules can handle a large range of situations.
7. Genetic Algorithm: 1. Initialize the population, P1 2. Create an empty population P2. 3. Select two individuals from P1 base on fitness criterion 4. Optimally mate and replace with offspring 5. Optimally mutate the individuals 6. Add the individuals to P2, until P2 is full. Let P1 be equal to P2.