Homework # 1

Chapter Review:


Eiben & Smith (2003). What Is an Evolutionary Algorithm? (Chap 2) In: Introduction to Evolutionary Computing. Springer.

The objective of the text is to describe the main characteristics of an evolutionary algorithm (EA). According to the authors, there are many variants of EA, although the basic idea is: “given a population of individuals within some environment that has limited resources, competition for those resources causes natural selection.” Translating for an optimization problem, in a function to be maximized, the quality of solutions, measure by the objective function, increases at each generation, due the evolutionary process. There are two drivers of the evolution process: variation operators (recombination and mutation) responsible for increasing the diversity within the population, and selection, which exclude the worst individuals and increase the quality of the solutions.

The main components of EA are: representation (definition of individuals), evaluation function (or fitness function), population, parent selection mechanism, variation operators (recombination and mutation), and survivor selection mechanism (replacement).

The first component in an EA is the representation, which means defining the how the solutions (individuals) are represented within the algorithm. Several syntaxes can be used. The terms candidate solution, phenotype, and individual are synonymous and denote points in the decision space. The terms genotype, chromosome and again individual represent points in the space where the evolutionary search happens. The transformation from the phenotype to the genotype space is called encoding, while the opposite is called decoding.

The second component is the evaluation function. Under the evolutionary perspective, the evaluation function represents the requirement the population should adapt to. In the algorithm, it measures the quality of the genotypes. Another terms used are fitness function or objective function.

The population is a multiset of individuals or genotypes. The population size can vary during the run. An important characteristic of the population is diversity, because it increases the chances of finding a global solution.

The parent selection mechanism is responsible for increasing the quality of the population by selecting better individuals to become parents of the next generation. Also called mating selection, an individual is selected based on its quality and also probability.

News individuals are created from old ones by the variation operators. Mutation is a unary operator applied to one genotype, generating a slightly different individual (mutant). This process is always stochastic. The purpose of mutation is to introduce diversity in the population, so a larger space is explored, decreasing the chances of population being trapped in local optimums.

The second variation operator is the recombination or crossover. In this case, it is a binary operator, crossing genotype of two individuals into one or two offspring individuals. It is also a stochastic operator because which parts of the genetic material and how it is combined are dependent on a random process.

Survivor selection, environmental selection or replacement is the process of distinguishing individuals based on their fitness. It is a similar process of parent selection, but used in a different stage of the algorithm.

Another component of EA is the initialization. Usually, the set of individuals are seeded randomly.

The last phase of EA is the termination condition. The text list four typical criteria for termination: maximum CPU time elapses, total number of fitness evaluations, fitness improvement remains under a threshold value for a given period of time, and the population diversity drops under a given threshold.

-------------------------------------------------------------------------------------------------------------

Article Review:

Kim, E., Jha, M., and Son, B. (2005). "Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach." TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 39(4), 339-360.

Questions about the Article:

a. Many different methods have been applied for highway alignment optimization. What are the deficiencies and advantages of using these methods? Why was a GA chosen in this work?

b. What are the differences among the different scenarios tested in the problem?

c. How does the GA perform for each of the different scenarios? What are the major conclusions of the article?

Discussion:

According to the authors, there are many reasons why others methods than GA fail in solving the highway alignment problem. Some of the defects are: necessity of differentiable objective functions, discontinuity, trap in local optima, output not smooth, applicability for implicit functions, inefficiencies, non-linear cost functions etc. GA was chosen in this work because the nature of the problem which involves constrained, non-linear, and non-differentiable structure, hardly solved by classic optimization techniques.

The differences among the different scenarios tested in the problem are the one and two-step optimization, the population size and the quality of the results. Scenarios 1 and 2 are one-step optimization with different population sizes, resulting in different quality of solutions. Scenario 3 is a two-step optimization. The first step is used to indicate the number of intersections, while the second step is run separately for each segment of highway. In this case there is a substantial decrease of computation time, and increase of quality of solution, in the present case, lower cost. In summary, the stepwise optimization improves significantly the results, and also results in better solution than the original procedure.