Evolutionary Computation Notes
Manuel de la Herrán Gascón
- ¿What they are?
- Let that it will be the ordering who make the work
- The bases of the AG: Struggle for the survival in a ambient of shortage
- The genetic, the reproduction sexual and the mutations
- Limitations of the life biological and the source of the eternal youth
- The fantastic mutant
- Selection Natural and Selection Artificial
- ¿When it is they can to apply the AG?
- ¿How to program AG?
- Options of a Algorithm Evolutionary
"We have a problem ¡That nuisance! Good, we go to to attempt to solve it. ¿We know how to make it? Not. then, to to prove. ¿We can to generate several solutions valid to that problem? Already, clear that we can, but go to be all very wrong solutions. Good, not import. The we generate: 40, 100, the that they will be. ¿Some is better that other? All they are wrong, but some they are less wrong that other. We catch the better, the other the we eliminate. ¿And now what? Good, the we can to catch of two in two and to mix them to to see if leaves something good ¿Yes? Good, to times operate. We go to to make it other time. And other. Also we can to mix them of other form. ¡Hears this it is stem, now they are all equal! Then, we go to to catch of time in when some of the wrong, not only of the good. ¿And if we make small changes to the random in small zones of some solution, to to see if some gives in the nail? Is worths... ¡Hears, this it is improving!"
¿What they are?
Within of the paradigms of learning automatic, the algorithms genetic it is present as one of the more promising in the road toward the intelligence artificial. Currently they have demonstrated its validity in multiple areas of application, and in any case, possess a great interest for the evident analogy that convert to the programmer in a creative of "life".
The steps that accomplish a AG they are:
1.- It is generate a joint of 1-N solutions valid to the problem. Normally, this(s) entities it is generate to the random. Values typical they are 20-200.
2.- It is evaluate the solutions existing, of way that it is eliminate some and it is maintain other (other possibility would be to limit the time of execution)
3.- It is permit the reproduction or recombinación of genes (normally for couples) of the entities existing. For example, it is accomplish crossings of standards to to depart of certain point elected to the random, of form that the new standards possess a segment of each one of the progenitors.
4.- It is effect mutations (changes to the random in the genes) of the new standards, according to a rate determined.
5.- It is continues in the step 2 until that it is find a entity that it is consider with sufcientemente weight or fitness
[ Back to Index ]
The algorithms genetic (AG) it is they can to understand as a strategy more of search, to the equal that the known "to it Broad", "in Depth", To escalate-Hills, Better-First, and To*. The algorithm selecciona a series of elements trying of to find the combination optima of these, using for this the experience acquired in previous combinations, stored in some standards genetic. Without embargo, in this case, the possibilities of this methodology transcienden of the search heuristic, had to to a reason of weight: the algorithm not work Top-Down, but Bottom-Up: is to say, not is necessary to have of a knowledge deep of the problem to reslover, for that this could be decomposed in sub-problems, but that it is part of structures simple that interactúan, letting that it will be the evolution who make the work. Solely enough with be capable of to identify cualitativamente in that cases the standards it is approach or it is remove of the solution sought, for that the system it is perfect automatically, developing its own behaviors, functionalities and solutions. Certainly, it is puede to say with humility that this technical there is demonstrated already its relative usefulness, in the life biological, creating us to we same.
Let that it will be the ordering who make the work
[ Back to Index ]
Given the increased rate -geometric- of reproduction of all the beings organic (Malthus), its number tend to to grow to pace exponencial, and given that the foods, space physical, etc. not it make in the same proportion, and while this occur, will born many more individual of the that is possible that survive, and in consequence, as it will be that generally it is appeal to the struggle for the existence, already it will be with individual of the same kind or of kinds different, or simply with the environment, attempting to modify its characteristic adverse, it is detach that a individual, if acts of a manner profitable for he, will will have a greater probability of to survive, and it will be seleccionado naturally.
The bases of the AG: Struggle for the survival in a ambient of shortage
The theory of the selection of the kinds (Darwin) support that those individual of a population that possess the characters more advantageous will let proportionally more descendents in the following generation; and if such characters it is they should to differences genetic, that they can it be transmitted to the falling, will tend to to change the composition genetic of the population, increasing the number of individual with said characteristic. Of this form, the population completes of beings live it is adapt to the circumstances variable of its environment. The result final is that the beings live tend to perfecciónarse in relationship with the circumstances that the implicate.
[ Back to Index ]
In a AG it is establish a relationship between each a of the possible solutions to a problem, and a code genetic, standard or chain of information, that of some form the represent. This code genetic it will be able to suffer mutations, it be transmitted to the descendents and it be combined with other through reproduction sexual. The code is seleccionado naturally deciding if it is maintain or not in the system. Also puede be evaluated quantitatively, assigning to him a weight.
The genetic, the reproduction sexual and the mutations
In the reproduction sexual, the information genetic of both progenitors it is combine it being generated the code genetic of a new individual. Furthermore, exist a certain probability of that in this process it is produces some mutation (variation to the random) of the material genetic resulting.
The reproduction sexual has the advantage of that combine two (or more) blocks of genes that already they have proven its efficiency, of way that is possible that the standard resulting inherit the characteristic desirable in both progenitors, in whose case it will be seleccionado, increasing the existence of said characteristic in the population. Precisely, more of the 95% of the kinds live in the planet possess reproduction sexual.
It more simple is that the standard represent directly a solution. For example, if the solution that i seek is the sequence of actions with the that it is procures a determined objective, the standard 234, 523, 12, 765, 256 would to represent said sequence of actions, if it is there is assigned previously to each number a action.
Without embargo, many times this not is possible, or not it is find usefulness in the combination of the chains generated (for example, if the if combination of two chains of information interesting generate normally a chain with a weight under), of form that the reproduction sexual -for combination- not represent no advantage. The solution is that the chains not represent directly the solution sought, but that it make of form indirect.
In the life biological occur something thus: in reality, the genes, more that to determine directly the characteristic that define a new individual, define a joint of rules of development that applied and combined will provoke said characteristic. For this, the endowment genetic, that exist in all the cells of each be live, control the accomplishment of certain reactions chemistries, of way that the genes they are the that determine, but not directly, the constitution and behavior of said individual. Some aspects fenotípicos, as the color of the eyes, they can determinarse genetically of a form quite direct, but the majority of the characteristic of a be live, as the type of sangre, the weight or the altura, not have a translation genetic tán simple, if well is certain that also many of the characteristic of a be live, as the weight, they are influidas for the ambient (for example, for the dieta).
Of the same form, the standards that we we believe not always they will be able to represent directly the solution sought. For example, in the problem of the travel you, that it must to travel several cities until to return to the point of departure incurring in the minimal cost, if the chains represent sequences of cities in the order in that it is travel, the probability of that through the combination of two chains valid, to to depart of a point to the random, it is generate a chain valid is decrease: much more it it will be the that the chain inherit the qualities positive of its progenitors.
In these cases, we will have to to change the position of work, and to make that the standard not it will be the solution in yes same, but "something" that it provoke, as a joint of methods, directors, rules, etc of search of the solution, that they will be easily combinables. Curling the curl, this standard puede be the joint of parameters that define the manner of execution of other AG, with it that we will will have AG hierarchic.
[ Back to Index ]
Seem to exist consensus in the community scientific in how much to that the information genetic flow solely in a address: from the genes toward outside. Is to say, the characters acquired to it long of the life not they are heirs, already that not exist route some that scope and modify the genes created in the conception. In the life biological not is possible the transmission genetic of the characteristic acquired or learnt, but this yes is possible in the life artificial. ¿Will exist some reason for the that would not be beneficial? In any case we the programmers not we are obligators to to observe said norm.
Limitations of the life biological and the source of the eternal youth
Exist other many limitations in the life natural or wet, that not exist in the life dry: the beings of life artificial not age. A standard it is puede to maintain indefinidamente, without that its qualities it is deteriorate.
[ Back to Index ]
Though is little probable that a change anyone in a gene it will be beneficial, the mutations produce several advantages: hinder the stagnation of the population increasing the variety, of way that before a change sharp of the environment, the community could it be adapted to the new situation; furthermore, permit the generation of any segment of standard, of way that if in the joint initial of standards not it is find all the elements necessary for to form the optimum, it will be possible to arrive to she.
The fantastic mutant
In some cases puede to occur that the standard sought could it be formed easily to to depart of combinations of standards that not it is consider very advantageous. The algorithm genetic it must to permit the existence of these standards. This is one of the principal problems of the AG, and even of the theory of the evolution: ¿How they have been able it be generated gradually organs complex, as the pens for the flight, if only the organ thoroughly functional is useful to the individual? Not always is easy to explain all the features that present a organization with a mechanism adaptativo.
[ Back to Index ]
The principal difference conceptual between the selection natural (or that it is produces without intervention of the man), and the selection artificial that we we establish our farms or in our programs, is that the selection natural not is properly a selection. We we can seleccionar for the reproduction the beings that more us interest, already they will be the cows more dairy or the agents software that better solve a problem. In change, in the nature not exist -in principle- a intelligence foreign that determine the address of the evolution. And without embargo the evolution yes it is produces. If in fact, not exist something or someone that control the evolution of the life in our planet, then we same we would be the example of a principle basic and universal: that the life, the intelligence, the conscience and who knows what other types of complexity in the future, they are events inherent, unavoidable and spontaneous of our universe. To this also it is to him there is call Darwinismo Universal, and suppose that all life, in any place, there is evoluciónado for means darwinianos.
Selection Natural and Selection Artificial
The program Land is a example of how agents software they can evolucionar without that it will be necessary a selection directed for a entity expresses. So much in this program as in other, exist a series of components software of some type capable of it be reproduced and to suffer mutations. In a Algorithm Genetic, the agents they should to solve a problem particular, but in Land the agents not make nothing more that it be reproduced. The space of report limited produces a selection natural, already that only the better entities they will be able let descendents in he. The existence of small mutations random enough for to generate agents with characteristic very complex, capable of to invade or to co-operate with other agents. After of to study a of these simulations, seem logical to suppose that in our planet there is been able to happen something seemed. It is quite extended the idea of that the first entities repliants emerged to the random, to to depart of the combination of elements, and that the selection made the rest. Without embargo Thomas Ray decided that its program began with a first agent capable of it be copied to yes same, without to intend that this autocopia it is produced spontaneously, as made Steen Rasmussen. It is outline the issue of yes the probability of appearance of the components basic of the life is too decrease for a alone planet. Fred Hoyle suggest the existence of a bombardment of material genetic of the foreign, -already it will be with or without entity conscious behind of this-, it that would give a greater margin, to the have been able to emerge this "first repliant" in any other world. Furthermore, this would solve some other problems, as the apparent "jumps of complexity" evolutionary. Is surprising the appearance of organs complex as the eyes, that with difficulty they have been able to emerge of a evolution gradual if not provide no advantage to the individual until that not it is find formed for i complete. The lamarkismo, is to say, the transmission genetic of the characters acquired, it is resuscitating, and Maximum Sandín offer other interesting explanation to all these problems through infections of type viral capable of to affect quickly to great part of the population.
In my opinion, the issue more passionate of the with difficulty explained for the darwinismo is the of the appearance of feelings of pleasure and pain in the beings live. We we can to assign to each agent a variable with a number call pleasure or pain, but not is necessary that the entity has actually those sensations for that it is behave as if the i had. Such time we could to build some day robots that it is behave as beings human, but ¿We will be able to make that sit? And though we could, ¿For what to make it? ¿For what it there is fact the nature with we? A thing is the life artificial as imitation of the processes own of the life, and other very different and to the that yet not it is there is arrived is the recreation of its essence, (or to the demonstration of that this not exist). The theories on the life and the evolution they are with difficulty demonstrable, and the discussion is intensive. Would to seem that these problems only relate to the biologists and philosophers, but not is thus. We recall that it is try of to create intelligence in our ordering imitating the form in that it made the nature. Without embargo, not we can to make it without more. We should to capture to the maximum the essence of all the process for to avoid that our ordering late million of years in to arrive to the solution waited.
[ Back to Index ]
In first place, in the problem to to solve, the goal there is of power be observed in degrees cualitativamente comparable. For other part, the principal difficulties to the hour of to implement a AG they are:
¿When it is they can to apply the AG?
- To define a structure of data that could to contain standards that represent, the solution optimum sought (unknown) and all the possible alternative of approximations to the solution.
- To define a type of standard such that if a standard is seleccionado positively, that this not it will be had to to the interaction of the different segments of the standard, but that exist segments that for yes alone provoke a selection positive.
- To define a function of evaluation that seleccióne the better individual.
In the algorithm we will be able to vary to our pleasure:
- Number of entities initial
- Method of generation of these entities (to the random or according to a function)
- Rate of reproduction (constant, variable according to a distribution statistics determined)
- Rate of deaths
- Method of reproduction: asexual, sexual with 2 progenitors, 3, etc.
- Rate of mutation (constant, variable)
- Types of mutations produced
- To permit or not the transmission genetic of the experience
- All type of restricciones that make that the operation of each one of the aspects previous depend of of certain conditions.
The algorithms genetic it is they can to complete (and to complicate) with multitude of aspects known of the life biological and other even not existing in the nature, without more limit that the imagination, entering in the world of the Artificial Life, where it is they can to observe behaviors social complex.
[ Back to Index ]
There is two aspects important of the programming of Evolutionary Algorithms that suppose certain differences with respect to the programming customary.
¿How to program AG?
The first is that is many more difficult to detect mistakes in the programming, already that great multitude of the lines of code it is will use solely as improvements on a plan initial of evolution, and in many cases the program will operate and even will offer good results executing functions wrong, or that to the less not make it that we we believe that make.
This it is puede to solve with more programming. A possible solution is to establish two manners of execution of the algorithm (Manner "Normal" and Manner "Detection of mistakes") of form that in the second manner it is execute certain checkings on the processes executed, accomplishing the tests in manner "Detection of mistakes" and distributing the application in manner "Normal".
But there is aspects much more interesting. If something it is learn programming Evolutionary Algorithms is that the ideas genial not always it they are. Already i have commented that great multitude of lines of code consist in improvements on a plan initial of evolution. Is very current the existence of parameters that though reduce the number of cycles necessary for to arrive to the type of entity that we seek, in the practical not they are profitable given the increase of the duration of the cycles.
As in the case previous, the solution is still more programming. When we program a "idea genial" is interesting to envisage always in the program both options, is to say, the incorporation or not of that idea, and to compare the results in various situations. Here is where it is the real problem, already that options that they can be prejudicial in executions short they could be very útiles in executions more release (problems more complicated), and precisely these tests not always is possible to make them.
It same occur in the nature: the "ideas genial" for to solve problems ecological they can not be it (and here it is sample a time more the usefulness of the simulations for ordering). In Australia it is attempted to combat a plague of rabbits inoculándoles the disease of the mixtomatosis. The population of rabbits reduced drastically, but to the end of a time it is arrived to the same population of rabbits... but now all resistant to the mixtomatosis. ¿It is produced then a mutation just when it is was needing? Probably not, the mutation was existing already, the possibility was, latent, in some of the rabbits, that quickly extended its genes.
These problems have furthermore a analogy and a "moral" that i i consider fundamental for the study of the evolution: in the Computation Evolutionary we find that reflections and hypothesis that to all lights seem certain, of a total evidence for our mind, result be thoroughly untruthful when the we program. Seem that occur it same moved to the earthly of the evolution of the kinds in the nature, including the humanizes. The Lamarkismo or the transmission of the characters acquired is a hypothesis with a logic aplastante; and without embargo resulted be untruthful. Well, since when remain established without place to doubts that the lamarksimo not exist, emerge voices critical that also with great coherence argue it opposite. This is still more important in aspects as the cooperation. In my opinion, in the Evolution (as in all field of study, but such time here more that in no other part), is very advisable to maintain a strong skepticism, to extract conclusions, for supposed, but without to forget never the other alternative.
[ Back to Index ]
The Computation Evolutionary (CE) is a term relatively new that attempt to group a batiburrillo of paradigms very related whose competitions not they are yet very defined. Until makes little was common to speak of Genetic Algorithms (AG) in general, in time of to identify different types of CE, already that the rest of the algorithms it is they can to interpret as variations or improvements of the AG, more known. In a AG the elements of the chains (genes) they are typically bits, and in certain cases, values numerical or strings. For its part, in the Strategies Evolutionary the elements of the chains they are values real that act as rules that define how is going to to act the individual before certain situation, and in the Programming Genetic they are instructions in a language of programming. Simulated Annealing it is puede to consider a simplification of the AG whose origin it is in the procedures physical of solidification controlled. The Classifiers Genetic solve problems of recognition of standards through a training base in examples, storing in the chains information that relate the data of entry and the exit wished. Finally, to me me like to consider the Artificial Life as a superconjunto of all these technical.
Options of a Algorithm Evolutionary
The new sciences always happen for a phase initial of confusion and inconsistency until to arrive to some conventions accepted for all. More or less the classification accepted in our days is
The approach subsimbólico of the I it is carácteriza for to create systems with capacity of learning. This it is puede to obtain to level of individual imitating the brain (Nets Neuronales), or to level of kind, imitating the evolution (CE)
Though exist other plans, for it general, these programs begin with a phase of initialization of the entities and its environment, and subsequently execute repetitively cycles within of the which we can to distinguish three stages:
Evaluation: it is try of to assign a value of weight or fitness to each individual, in function of it well that solves the problem.
Selection: now we should to classify to the agents in four types, according to survive or not, and according to it is reproduce or not, in function of the weights.
Reproduction: it is generate the new individual, it being produced some mutations in the births.
In reality the two first phases it is they can to fuse in a, already that not is strictly necessary to assign to each entity a weight, but simply to know which they are better that other, but to assign weights tend be it more comfortable. Also we can to combine the second and the third generating the new entities solely in the zone of report where it is find the agents to to eliminate, and to maintain thus the population constant. In any case, always will exist some form of evaluation, selection and reproduction. Each one of these processes it is puede to accomplish of many forms different, independently of the problem that it is it be resolving.
In the following table it is summary some options of a algorithm evolutionary. We can to devise many more. In general it is try of different forms of to produce, or well a convergence more rapid toward a solution, or well a exploration more to fund of the space of search. Both things they are desirable and contradictory, for it that it is there is of to arrive to a commitment. This commitment is it that before i have call cooperation. For supposed that all this not they are more that metaphors. It is require of a force conservative (development-selfishness), that benefit to the better agents, is to say, to the that better solve our problem. This is evident, but not enough. Also is necessary a force innovative (exploration-altruism), that permit the existence of agents very different, yet when its weight it will be smaller. Thus it is puede to obtain the variety sufficient for to avoid a population stagnant in a maximum local, and to permit the resolution of problems changing or with several maximum. This occur of form spontaneous in the nature for be something inherent to each entity, that puede be seleccionado, but result more comfortable to program it of form expresses, is to say, we will make that our program seleccióne for the reproduction "the agents good", but also "some how much of the bad" for to maintain the variety.
- Number of entities.
- Number of elements (genes, rules) for each agent.
Method of Evaluation: Asígnar a weight
- To disorder the entities before of to evaluate them
- Different forms of modification of the weights after of the evaluation. For example, the weight of a entity it is puede to calculate independently of the other entities, or it is puede to modify thereinafter this value, reducing the weight if exist other entity very similar, analyzing for this a certain subset of the population neighboring.
Method of Selection: ¿Who dies? ¿Who it is reproduce?
- With or without reemplazamiento
- Method of the roulette
- Method of the tilts
- Selecciónar the n% better and the m% worse
Method of Reproduction: To generate and mutar new children - The parents they can it be taken for couples or in groups more numerous, elected to the random or in order of weights
- In the case of to detect that the progenitors they are very seemed, it is puede to accomplish a action special, as to increase the probability of mutation
- The entities they can to communicate to other its knowledge, already it will be to all or to a part of the population, directly or to slant of a blackboard, (a kind of tablón of announcements)
- Method of recombinación of genes: it is puede to take genes of one or other progenitor to the random, in a certain order, with one, two or more points of court, etc.
- Rate of mutation variable
- To fix a rate of mutation different for each individual or even for each gene
- To make that it will be more probable that it is produces a mutation in a gene if in its neighboring already it is there is produced
- To substitute for mutations genes without usefulness, as rules wrong or repeated
- Types of mutations
The types of mutations require of a greater explanation. When the genes they are bits, a mutation consist in to invest a bit, but ¿how mutar genes when each gene puede to take but of two values? We suppose that we have a problem with three variable of 8 bits each a. We would would have chains as:
We go to to suppose that is probable that exist zones of values good and wrong; is to say, that if the 7 is a good value and the 200 bad, it will be probable that also the 8 it will be good and the 199 bad. Would be interesting that the mutations us permitted to move us (to change of value) slowly and with accuracy if we are in the zone good, but also rapid and jerkily for if chance us we found in the wrong. This it we can to obtain precisely changing a bit to the random, already that us we move slowly changing bits of the part straight, and quickly with the of the left. In change, if the mutation consisted in to change the value of all a variable for other anyone, having all the same probability, we will be able to move us quickly, but not slowly (to the less, with a probability decrease), with it that we would lose values interesting. If the mutations consisted in to increase or to subtract one of form regulation, we could to move us slowly, but not quickly, with it that would cost much to leave of the zone wrong. In definitive it is try of, given a value, to define the probability of to happen to each one of the values remaining.
We have supposed that exist zones of values good and wrong. If this not it is fulfilled we could simply "to increase one" of form regulation, for to travel all the values how much before. In general it is observe that the mutations to level of bit they are the more adapted, though not always occur thus. In any case, when we combine two chains we will have to to act to level of variable, and to combine variable complete. Of it opposite we would be generating multitude of mutations simultaneous, breaking for any place values that they can be valuable.
¿What options they are the good? Such time it will be possible to determine to simple sight if a election is adapted, but in the majority of the cases it will be necessary a irksome process of test, already that the kindness of some puede to depend of the election of other. If something it is learn programming algorithms evolutionary is that the ideas genial not always it they are. Is very current the existence of parameters that though reduce the number of cycles necessary for to arrive to the type of entity that we seek, in the practical not they are profitable given the increase of the duration of the cycles.
To execute all the possible combinations of options is inconceivable ¿Not it will be possible to analyze several in a only algorithm, in different moments? ¿And that such to analyze several options simultaneously, in fractions separated of the population? Is to say, ¿We can to create algorithms evolutionary autoconfigurables? For to answer to these questions is interesting to group all the aspects and options in four categories, according to the table.
Type gene The aspects of type gene they will be those that, as the genes, they are different within of a same individual. Type individual The aspects of type individual they are those that it is maintain equal in a same individual, but defer of some agents to other. Type island The aspects of type island they are those that they are equal for a subset of individual; of more of one, but without to arrive to the total. Type population The aspects of type population they are the that they should be equal for all the population.
The options or aspects of type gene they can it be proven introducing them as part of each one of the genes, within of each one of the genes. If it is wants, it is puede to think in a counterfoil of two dimensions more that in a chain of genes. We go to to see it in the case of a program that learn to to play to the tic-tac-toe. Each one of the genes is a rule that says how to play before determined situation. Before of to accomplish a movement, the agent prove what rules puede to use and chooses a of they. ¿How to choose it? We could to think in to associate initially to each rule a priority arbitrational fixes, and to choose the of greater priority. Other form would be to assign to each rule a weight that it is increased each time that said rule it would be used in a departure cattle, and to apply the rule that in more victories there is participated until the moment. For to carry to the practice anyone or the two options combined, will suffice with to include the information as part of each gene. If before each gene was a rule, now each gene it will be a rule, more a value of priority, more a weight. Other option of type gene would be to assign a probability of mutation different for each element of the chain, of form that the genes, after of be heirs, may have different probabilities of mutarse. If in a determined moment, certain value of a gene it is sample as very useful, puede be interesting that its probability of mutation reduce, and conversely.
The aspects of type individual they can it be proven introducing them as if they would be new genes, to continuation of the that already exist. The rate of mutation, though tend be equal for all the population, and we have seen that would be even different for each gene, would also be different for each individual, of form that the children of certain agents may have greater probability of to possess mutations. For example, in the tic-tac-toe, a entity it will be compound for a joint of rules more a probability of mutation. This value it is it will be able to inherit and mutar, and if is useful, it is will see seleccionado, equal that a rule anyone. Before we have spoken of to assign a priority to each rule. The priority associate to each rule is a aspect of type gene, but the decision of to associate or not priorities to the rules is a aspect of type individual, that it must to affect compulsorily to all its rules.
To prove and to implement aspects of type island is going to be more complicated. For example, we suppose that we want to prove that would occur if we permitted to our insects to share its knowledge, is to say, it be transmitted information genetic in form of infection viral, such as report Maximum Sandín. We could to create several islands or sub-groups of agents with different options, maintaining them separated for a barrier of some type that not permit the contact of some with other. More late we could to compare the knowledge obtained in each island or even to assemble of time in when to some or to the better of each group for the reproduction. The options of type island they can be evaluated automatically without to modify much the algorithm, already that is of to wait that the groups with worse options it is extinguish. The idea general is that so much for groups as for individual or genes, it good survive and it bad perish. For to create barriers, we can to define types of kinds different that only they are capable of it be reproduced between yes, possessing each a of they, for example, different methods of recombinación of genes, with one, two or more points of court in the crossing, or even conceiving of form different the points of beginning and end of the units minimal that it is recombinan (genes). Curiously, in this case, the own method of implementation of the barriers (types of reproduction incompatible) is precisely that that we are proving. For to implement it we can to add a gene special to each agent of form that only the agents with the same value in said gene they will be capable of recombinarse between yes. Each value will correspond with a option different. For to prove more of a we will have to to put several of these genes, and to compel to a coincidence in all they.
The options of type population only they can it be proven executing algorithms in parallel. These options they are the more general, as the number total of agents or the number of rules that has each individual. Other example of type population is the fact of to adjust the weights of the agents, of form that if already exist other agent seemed to the that finish of to born, it is reduce the weight of the new agent. This option not puede be applied only to a part the population, already that it is would see in obviate disadvantage. To evaluate options of type population is it more complicated. We will have to to create algorithms independent and to compare them, for example, in the tic-tac-toe, provoking a departure between the better entities of each a of the simulations, is to say, creating other flat superior of game.
Algorithms hierarchic I go to to change of point of sight for to analyze the hierarchies within of the algorithms evolutionary. In a algorithm genetic, the reproduction, selection, mutations, assignment of weights, etc. it is develop to a only level or flat. Without embargo, in the case of the tic-tac-toe, exist several flat.
In the flat more increased, play the ordering against the man. This game puede it be interpreted as a algorithm evolutionary reduced to its minimal expression, with a population of two individual, where the algorithm end to the to end the departure. In this type of problems have quite success the paradigms in the that the ordering try of to learn observing the game human, but not is this the case. For to learn, the ordering create a second level of game, where many entities will play for couples. That entity that more departures earn it will be the that represent to the ordering in the game against the man. But still it is puede to speak of a third level, already that within of a same agent, each a of the rules puede to possess also a weight, and though the rules not it is reproduce combining its elements (they could to make it), is possible to substitute some each certain time.
Already that the entity of level superior there is created a sub-world or flat where play several sub-entities, thanks to the which is capable of to learn for its account before of to play against the man, these sub-entities they could to its time to create other flat that you provided knowledge, until that arrive the moment of to play "of truth". Is to say, a entity, to the equal that to play, or it be reproduced, would also to have a action that we could to call "to think" and that consisted in to experience departures hypothetical (hypothetical for the entity superior; to the inferior to him will seem the his so real as to any other), creating "worlds virtual", of the same form that the persons we imagine or we believe hypothesis for to anticipate the events.
This would be furthermore a plan where to implement the algorithm minimax typical of the games, where the agent evaluates possible movements own and of the opposite to several levels of depth. We can to combine this type of hierarchies with the relative to the election of options of type population. Is to say, while we seek the solution to our problem initial in the algorithms or flat inferior, we can to experience in a flat superior some options, the which they can to its time to have subopciones.
The "problem of the deception", "epístasis" or "absence of blocks constructing"
A chain of a algorithm evolutionary has several elements (genes) that correspond with variable of the problem to to solve. Puede have genes whose values they will be intrinsically good or bad, is to say, good or bad independently of the values of the rest of the chain. We go to darles a name to this type of genes, for example, genes not-linked. Consequently, a gene whose kindness or wickedness depend of the values of some of the other genes it will be linked.
The property of be or not linked puede it be applied also to a joint of elements of the chain, if have in account all they together, as a only gene, without to require that they will be contiguous. We imagine a problem in the that all the genes they would be not-linked: ¡Not would be necessary a algorithm evolutionary! For to find the values optimum of the variable, would suffice with to analyze independently all the possible values of each gene, maintaining constant the rest of the chain with any value. We imagine now that all the segments they are linked, less two, is to say, all the genes they are intrinsically good or bad, except two, that depend of other. Yes, but ¿of which? ¿The one of the other? ¿Both of all the remaining? If the kindness of each one of these two segments only depended of yes same and of the value of the other they could be treaties in joint as a only gene not-linked, and to apply the same process. If the kindness of the genes linked depended of all the other we will be able to use the same method, having the caution of to calculate first the values of the segments not-linked.
We imagine now the case extreme of that all the genes they will be linked, and all depend of the value of all the other. This not would be a problem irresoluble, but yes the worse that us we could to find, not only for the technical evolutionary, but for any other method. Would be something thus as to seek a object with the eyes closed, and the better form of to try it would be, logically, a search sequential. In any case, it that more us interest is to seek segments and groups of segments not-linked, though they will be large, already that if we can to divide the chain in several segments not-linked we will be able to apply a algorithm independent for each segment, in the that the rest of the chain it will be always fixed, with a value anyone, and to obtain the solution much more rapid.
For to know if a element (or a joint of elements) is not-linked we could to fix values to the random for the rest of the chain, to evaluate the chains that result of all the possible combinations of values for the joint of elements elected and to store the order of the chains ordered according to its weight. If repeating the process using different values in the rest of the chain, always we obtain the chains in the same order, then we will be before a segment not-linked. Other form would be to prove estadísticamente if in different cycles of the algorithm, the same values for a segment produce positions relative similar within of the ready of agents ordered for weight. For example, if a variable puede to take values of 1 to 10, we can to store, for each value, which is the position mean that occupy the chain that the contain, within of the ready of chains ordered for weights, in each one of the cycles.
Other form of to find the vinculaciones would be to define them to the random and to act as if of fact existed, proving if of this form it is obtain better results. For last, i go to to present the that me seem the form more easy of all. For the algorithm is much more simple to find the values optimum of the segments not-linked that the of the linked. For so much, after of some how much cycles, the genes of values more homogeneous will will have a greater probability of be more not-linked that the rest. The genes linked it is behave in reality as a only gene, for it that it is there is of to avoid its division. It is me occur that we could to obtain some advantage if we compel to that exist a kind of cohesion between the genes linked, is to say, between the segments of values more heterogeneous, of form that it is inherit and muten together, simultaneously, with a greater probability.
[ Back to Index ]
¡You are guest to to hold, criticize and collaborate with your ideas!
Send your commentaries, questions, suggestions, or criticize to to the following address:
[ Home Page Spanish | Home Page English ] The software of Gaia is free, sources available. There is not
commercial interests, only to research and amusement.
You can send your suggestions about
the face of the web or its contents to the E-mail