1

I am basing my question on the pseudocode for the CHC Adaptive Search Algorithm by Eshelman given in this answer by deong:

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

How does this algorithm deal with situations where the child population has lower fitness than the parent population?

Consider a population of two parent with a large enough hamming distance to produce children. Now if both children have a lower fitness than their parents, doesn't the survivor selection ("take best n") select the same parents again, resulting in an infinite loop?

xnor
  • 113
  • 3

1 Answers1

0

CHC never has a next generation's population with lower fitness than the current one due to the use of a truncation selection step. It combines the parents and offspring, sorts by fitness, and takes the best $n$ individuals. So if including any child would lower the fitness of the population, it would just select the parents as the next generation and the average fitness would stay the same.

In principle, you could indefinitely select the same two parents over and over, continually producing inferior offspring. But generally you're running CHC with a population size of 50 or more, so you don't expect to continually pair the same two parents. Also, it's technically an infinite loop anyway, as most GAs are. In practice you define some stopping condition based on evaluation count or wall clock time or whatever.

deong
  • 804
  • 5
  • 5
  • With "child population" I wasn't referring to the resulting population of the selection step, but all the children of the parents. In the pseudo code you called this the child population ("take best n individuals from union of parent and child populations"). By selecting from the union of both these populations, the result (the "next population") of course will never be lower in fitness. But the rest of your response answered my question perfectly. Thanks. – xnor May 24 '18 at 21:03
  • No, when I said child population, I meant the offspring following selection and crossover. In CHC (and most GAs really), there's no reason you need to perform selection as a separate operation with a separately stored population. You must have the current population, you select parents from it, cross them over, mutate if necessary, and out the children into a new population. When that new population is full, select the contents of the next generation to put into the main population. – deong May 26 '18 at 00:13
  • Ah, by "selection" I meant "survivor selection" not "parent selection". Sorry for the confusion! I wlll also update the question to remove this ambiguity. – xnor May 26 '18 at 11:21
  • So to clarify why I commented in the first place is this in your answer: "CHC never has a child population with lower fitness than the parent ". Here you seem to refer to the next population (the result of survivor selection of both parent+child populations) confusingly as "child population" again. But the actual population of children could have lower fitness. Maybe you want to clarify that first sentence in your answer for other readers. – xnor May 26 '18 at 11:55
  • Oh, yeah I see that now. You're right, that was confusing. – deong May 27 '18 at 18:21