CS614 Handouts Spring 2025 by MS

Lecture No. 11-13

3 Genetic Algorithms

3. 1 Discussion on Problem Solving

In the previous chapter we studied problem solving in general and elaborated on various search strategies that help us solve problems through searching in problem trees. We kept the information about the tree traversal in memory (in the queues), thus we know the links that have to be followed to reach the goal. At times we don’t really need to remember the links that were followed. In many problems where the size of search space grows extremely large we often use techniques in which we don’t need to keep all the history in memory. Similarly, in problems where requirements are not clearly defined and the problem is illstructured, that is, we don’t exactly know the initial state, goal state and operators etc, we might employ such techniques where our objective is to find the solution not how we got there.

Another thing we have noticed in the previous chapter is that we perform a sequential search through the search space. In order to speed up the techniques we can follow a parallel approach where we start from multiple locations (states) in the solution space and try to search the space in parallel.

3. 2 Hill Climbing in Parallel

Suppose we were to climb up a hill. Our goal is to reach the top irrespective of how we get there. We apply different operators at a given position, and move in the direction that gives us improvement (more height). What if instead of starting from one position we start to climb the hill from different positions as indicated by the diagram below.

In other words, we start with different independent search instances that start from different locations to climb up the hill.

Further think that we can improve this using a collaborative approach where these instances interact and evolve by sharing information in order to solve the problem. You will soon find out that what we mean by interact and evolve.

However, it is possible to implement parallelism in the sense that the instances can interact and evolve to solve the solution. Such implementations and algorithms are motivated from the biological concept of evolution of our genes, hence the name Genetic Algorithms, commonly terms as GA.

3. 3 Comment on Evolution

Before we discuss Genetic Algorithms in detail with examples lets go though some basic terminology that we will use to explain the technique. The genetic algorithm technology comes from the concept of human evolution. The following paragraph gives a brief overview of evolution and introduces some terminologies to the extent that we will require for further discussion on GA. Individuals (animals or plants) produce a number of offspring (children) which are almost, but not entirely, like themselves. Variation may be due to mutation (random changes), or due to inheritance (offspring/children inherit some characteristics from each parent). Some of these offspring may survive to produce offspring of their own— some will not. The “better adapted” individuals are more likely to survive. Over time, generations become better and better adapted to survive.

3. 4 Genetic Algorithm

Genetic Algorithms is a search method in which multiple search paths are followed in parallel. At each step, current states of different pairs of these paths are combined to form new paths. This way the search paths don't remain independent, instead they share information with each other and thus try to improve the overall performance of the complete search space.

3. 5 Basic Genetic Algorithm

A very basic genetic algorithm can be stated as below.

Start with a population of randomly generated, (attempted) solutions to a problem

Evaluate each of the attempted solutions Keep the “best” solutions Produce next from these solutions (using “inheritance” and “mutation”)

Quit when you have a satisfactory solution (or you run out of time)

The two terms introduced here are inheritance and mutation. Inheritance has the same notion of having something or some attribute from a parent while mutation refers to a small random change. We will explain these two terms as we discuss the solution to a few problems through GA.

3. 6 Solution to a Few Problems using GA
4. 6.1 Problem 1: Suppose your “individuals” are 32-bit computer words You want a string in which all the bits in these words are ones

rest)

Pick a random bit in the word and toggle (change) it Note that this procedure does not guarantee that the next “generation” will have more 1 bits, but it’s likely

As you can observe, the above solution is totally in accordance with the basic algorithm you saw in the previous section. The table on the next page shows which steps correspond to what.

Terms Basic GA Problem Solution Initial Population Start with a population of randomly generated attempted solutions to a problem Create randomly generated computer words

Evaluation Function Evaluate each of the attempted solutions. Keep the “best” solutions Count the 1 bits in each word. Exit if any of the words have all 32 bits set to 1

Keep the ten words that have the most 1s (discard the rest)

Mutation Produce next from these solutions (using “inheritance” and “mutation”) From each word, generate 9 new words as follows: Pick a random bit in the word and toggle (change) it