| 失效链接处理 |
|
Genetic Algorithms in Java Basics PDF 下载
本站整理下载：
提取码：3lrd
相关截图：
主要内容：
Population Size
The population size is simply the number of individuals in the genetic algorithm’s population in any one generation. The larger the population’s size, the more
of the search space the algorithm can sample. This will help lead it in the direction
of more accurate, and globally optimal, solutions. A small population size will often
result in the algorithm finding less desirable solutions in locally optimal areas of the
search space, however they require less computational resources per generation.
Again here, like with the mutation rate, a balance needs to be found for optimum
performance of the genetic algorithm. Likewise, the population size required will
change depending on the nature of the problem being solved. Large hilly search
spaces commonly require a larger population size to find the best solutions.
Interestingly, when picking a population size there is a point in which increasing
the size will cease to provide the algorithm with much improvement in the accuracy
of the solutions it finds. Instead, it will slow the execution down due to the extra
computational demand needed to process the additional individuals. A population
size around this transition is usually going to provide the best balance between
resources and results.
Crossover Rate
The frequency in which crossover is applied also has an effect on the overall performance of the genetic algorithm. Changing the crossover rate adjusts the chance
in which solutions in the population will have the crossover operator applied to
them. A high rate allows for many new, potentially superior, solutions to be found
during the crossover phase. A lower rate will help keep the genetic information
from fitter individuals intact for the next generation. The crossover rate should usually be set to a reasonably high rate promoting the search for new solutions while
allowing a small percentage of the population to be kept unaffected for the next
generation.
Genetic Representations
Aside from the parameters, another component that can affect a genetic algorithm’s performance is the genetic representation used. This is the way the genetic
information is encoded within the chromosomes. Better representations will
encode the solution in a way that is expressive while also being easily evolvable.
Holland’s (1975) genetic algorithm was based on a binary genetic representation.
He proposed using chromosomes that were comprised of strings containing 0s and
1s. This binary representation is probably the simplest encoding available, however
for many problems it isn’t quite expressive enough to be a suitable first choice.
Introduction Chapter 1
17
Consider the example in which a binary representation is used to encode an integer which is being optimized for use in some function. In this example, “000” represents 0, and “111” represents 7, as it typically would in binary. If the first gene in the
chromosome is mutated - by flipping the bit from 0 to 1, or from 1 to 0 - it would
change the encoded value by 4 (“111” = 7, “011” = 3). However, if the final gene in
the chromosome is changed it will only effect the encoded value by 1 (“111” = 7,
“110” = 6). Here the mutation operator has a different effect on the candidate solution depending on which gene in its chromosome is being operated on. This disparity isn’t ideal as it will reduce performance and predictability of the algorithm. For
this example, it would have been better to use an integer with a complimentary
mutation operator which could add or subtract a relatively small amount to the
gene’s value.
Aside from simple binary representations and integers, genetic algorithms can
use: floating point numbers, trees-based representations, objects, and any other
data structure required for its genetic encoding. Picking the right representation is
key when it comes to building an effective genetic algorithm.
Termination
Genetic algorithms can continue to evolve new candidate solutions for however
long is necessary. Depending on the nature of the problem, a genetic algorithm
could run for anywhere between a few seconds to many years! We call the condition in which a genetic algorithm finishes its search its termination condition.
Some typical termination conditions would be:
• A maximum number of generations is reached
• Its allocated time limit has been exceeded
• A solution has been found that meets the required criteria
• The algorithm has reached a plateau
Occasionally it might be preferable to implement multiple termination
conditions. For example, it can be convenient to set a maximum time limit with the
possibility of terminating earlier if an adequate solution is found.
The Search Process
To finish the chapter let’s take a step-by-step look at the basic process behind a
genetic algorithm, illustrated in Figure 1-10.
Chapter 1 Introduction
18
1. Genetic algorithms begin by initializing a population of candidate
solutions. This is typically done randomly to provide an even
coverage of the entire search space.
2. Next, the population is evaluated by assigning a fitness value to
each individual in the population. In this stage we would often
want to take note of the current fittest solution, and the average
fitness of the population.
3. After evaluation, the algorithm decides whether it should
terminate the search depending on the termination conditions
set. Usually this will be because the algorithm has reached a fixed
number of generations or an adequate solution has been found.
4. If the termination condition is not met, the population goes
through a selection stage in which individuals from the population
are selected based on their fitness score – the higher the fitness,
the better chance an individual has of being selected.
Figure 1-10. A general genetic algorithm process
Introduction Chapter 1
19
5. The next stage is to apply crossover and mutation to the selected
individuals. This stage is where new individuals are created for the
next generation.
6. At this point the new population goes back to the evaluation
step and the process starts again. We call each cycle of this loop a
generation.
7. When the termination condition is finally met, the algorithm will
break out of the loop and typically return its finial search results
back to the user.
CITATIONS
Turing, A.M. (1950). “Computing Machinery and Intelligence”
Simon, H.A. (1965). “The Shape of Automation for Men and Management”
Barricell, N.A. (1975). “Symbiogenetic Evolution Processes Realised by Artificial
Methods”
Darwin, C. (1859). “On the Origin of Species”
Dorigo, M. (1992). “Optimization, Learning and Natural Algorithms”
Rechenberg, I. (1965) “Cybernetic Solution Path of an Experimental Problem”
Rechenberg, I. (1973) “Evolutionsstrategie: Optimierung technischer Systeme
nach Prinzipien der biologischen Evolution”
Schwefel, H.-P. (1975) “Evolutionsstrategie und numerische Optimierung”
Schwefel, H.-P. (1977) “Numerische Optimierung von Computer-Modellen mittels
der Evolutionsstrategie”
Fogel L.J; Owens, A.J; and Walsh, M.J. (1966) “Artificial Intelligence through
Simulated Evolution”
Holland, J.H. (1975) “Adaptation in Natural and Artificial Systems”
Dorigo, M. (1992) “Optimization, Learning and Natural Algorithms”
Glover, F. (1989) “Tabu search. Part I”
Glover, F. (1990) “Tabu search. Part II”
Kirkpatrick, S; Gelatt, C.D, Jr., and Vecchi, M.P. (1983) “Optimization by simulated
annealing”
21
Implementation of a
Basic Genetic Algorithm
In this chapter we will begin to explore the techniques used to implement a basic
genetic algorithm. The program we develop here will be modified adding features
in the succeeding chapters in this book. We will also explore how the performance
of a genetic algorithm can vary depending on its parameters and configuration.
To follow along with the code in this section you’ll need to first have the Java JDK
installed on your computer. You can download and install the Java JDK for free from
the Oracle’s website:
oracle.com/technetwork/java/javase/downloads/index.html
Although not necessary, in addition to installing the Java JDK, for convenience
you may also choose to install a Java compatible IDE such as Eclipse or NetBeans.
Pre-Implementation
Before implementing a genetic algorithm it’s a good idea to first consider if a
genetic algorithm is the right approach for the task at hand. Often there will be better techniques to solve specific optimization problems, usually by taking advantage
of some domain dependent heuristics. Genetic algorithms are domain independent, or “weak methods”, which can be applied to problems without requiring any
specific prior knowledge to assist with its search process. For this reason, if there
isn’t any known domain specific knowledge available to help guide the search process, a genetic algorithm can still be applied to discover potential solutions.
When it has been determined that a weak search method is appropriate, the
type of weak method used should also be considered. This could simply be because
an alternative method provides better results on average, but it could also be
because an alternative method is easier to implement, requires less computational
resources, or can find a good enough result in a shorter time period.
Chapter 2
Chapter 2 Implementation of a Basic Genetic Algorithm
22
Pseudo Code for a Basic Genetic Algorithm
The pseudo code for a basic genetic algorithm is as follows:
1: generation = 0;
2: population[generation] = initializePopulation(populationSize);
3: evaluatePopulation(population[generation]);
3: While isTerminationConditionMet() == false do
4: parents = selectParents(population[generation]);
5: population[generation+1] = crossover(parents);
6: population[generation+1] = mutate(population[generation+1]);
7: evaluatePopulation(population[generation]);
8: generation++;
9: End loop;
The pseudo code begins with creating the genetic algorithm’s initial population.
This population is then evaluated to find the fitness values of its individuals. Next,
a check is run to decide if the genetic algorithm’s termination condition has been
met. If it hasn’t, the genetic algorithm begins looping and the population goes
through its first round of crossover and mutation before finally being reevaluated.
From here, crossover and mutation are continuously applied until the termination
condition is met, and the genetic algorithm terminates.
This pseudo code demonstrates the basic process of a genetic algorithm;
however it is necessary that we look at each step in more detail to fully understand
how to create a satisfactory genetic algorithm.
About the Code Examples in this Book
Each chapter in this book is represented as a package in the accompanying
Eclipse project. Each package will have, at minimum, four classes:
• A GeneticAlgorithm class, which abstracts the genetic algorithm itself and
provides problem-specific implementations of interface methods, such as
crossover, mutation, fitness evaluation, and termination condition checking.
• An Individual class, which represents a single candidate solution and its
chromosome.
• A Population class, which represents a population or a generation of
Individuals, and applies group-level operations to them.
• A class that contains the “main” method, some bootstrap code, the concrete
version of the pseudocode above, and any supporting work that a specific
problem may need. These classes will be named according to the problem it
solves, e.g. “AllOnesGA”, “RobotController”, etc.
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
