The Genetic Algorithm Traveling Salesman program:
Step By Step
1. Complete function replace-nth
(defun replace-nth (lst n elt)
"Returns result of replacing the N-th element of LST by ELT."
;;;Recursive function, use a cond form:
;;; If the lst is null, return nil
;;; If n is 0, cons elt onto the rest of lst
;;; Otherwise cons the first of ls onto ???? (recursive call goes here)
)
Test your function:
> (replace-nth
'(SEATTLE PORTLAND SPOKANE SPOKANE BELLINGHAM) 0 'WENATCHEE)
returns: (WENATCHEE PORTLAND SPOKANE SPOKANE BELLINGHAM)
> (replace-nth
'(SEATTLE PORTLAND SPOKANE SPOKANE BELLINGHAM) 2 'WENATCHEE)
returns: (SEATTLE PORTLAND WENATCHEE SPOKANE BELLINGHAM)
> (replace-nth
'(SEATTLE PORTLAND SPOKANE SPOKANE BELLINGHAM) 4 'WENATCHEE)
returns: (SEATTLE PORTLAND SPOKANE SPOKANE WENATCHEE)
> (replace-nth
'(SEATTLE PORTLAND SPOKANE SPOKANE BELLINGHAM) 6 'WENATCHEE)
returns: (SEATTLE PORTLAND SPOKANE SPOKANE BELLINGHAM)
2. Write function get-path
(defun get-path (individual)
"Returns the list of cities associated with INDIVIDUAL."
;; You don't have to use the word "return" in the code
)
Test your answer:
> (get-path
'((SEATTLE PORTLAND SEATTLE SEATTLE SEATTLE) . 0.64102566))
Returns: (SEATTLE PORTLAND SEATTLE SEATTLE SEATTLE)
3. Test the function chromosome-strength.
First you need to complete the function path-cost:
(defun path-cost (path)
"Returns the length of the PATH."
;; Recursive version:
;; if the length of the path is less than or equal to 1
;; return 0 (you don't have to use the word "return")
;; else add together the distance between the first two
;; cities in the path plus the recursive call on
;; the rest of the path.
)
Hint: Use the function "distance" that is already defined in the program.
Test your answer to the path-cost function:
> (path-cost '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE))
500
> (path-cost '(SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE))
0
The "non-tour-penalty" in this program represents a penalty for duplicate
cities. The penalty is 100 * number-of-duplicates.
Examples:
(SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE) 4 duplicates, 400 penalty
(SEATTLE SEATTLE PORTLAND WENATCHEE PORTLAND) 2 duplicates, 200 penalty
After writing the function path-cost, test chromosome-strength:
> (chromosome-strength '((SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE). 0)
returns: 0.5
> (chromosome-strength
'((bellingham spokane portland seattle wenatchee) . 0))
returns: 4.2918454936
> (chromosome-strength
'((SEATTLE PORTLAND SPOKANE WENATCHEE BELLINGHAM) . 0))
returns: 4.784688995215311
Note how two different successful tours generate different scores.
Why?
4. Write function mutate1. This takes one individual as a parameter.
This function must pick a random location in the individual
and a random city from list of cities.
Here are 3 sample runs of mutate1:
> (mutate1 '((SEATTLE SEATTLE PORTLAND SEATTLE SEATTLE).0))
returns: ((SPOKANE SEATTLE PORTLAND SEATTLE SEATTLE) . 0)
In the above example, "where" is position 0
and the "new-city" picked is SPOKANE
> (mutate1 '((SEATTLE SEATTLE PORTLAND SEATTLE SEATTLE).0))
returns: ((SEATTLE BELLINGHAM PORTLAND SEATTLE SEATTLE) . 0)
In the second example, "where" is position 1
and the "new-city" picked is BELLINGHAM
An alternative is to have the mutate1 function return the individual
with the chromosome strength calculated. For example, the example
above would return:
((SEATTLE BELLINGHAM PORTLAND SEATTLE SEATTLE) . 0.9132420)
5. Write function add-individual, which takes one individual as the
parameter and returns a new population with this new individual added
to the population. If population is filled, the individual with the
minimum strength is removed (assuming this minimum strength is lower
than the new individual to be added), and the new individual is
added to the top of the population.
Part 1: add a new individual to a population that is not filled:
> (add-individual
'((SEATTLE BELLINGHAM PORTLAND SEATTLE SEATTLE) . 0.9132420))
sets the current population to:
(
((SEATTLE BELLINGHAM PORTLAND SEATTLE SEATTLE) . 0.91324200913242)
((SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE) . 0)
)
This population has two individuals, the individual that was just added
and the original "starter" individual.
Note that the "starter" individual, 5 SEATTLE's, would actualy evaluate to .5
as a chromosome-strength. The "0" fitness level is the default fitness before
using the chromosome-strength function.
Part 2: Adding an individual to a population that is filled.
If the *current-pop-size* is greater than or equal to the population limit,
then it is necessary to check the new individual's strength with the
current minimum strength, *current-min-strength*. If an individual in the
population has a fitness value that is lower than the new individual's fitness,
remove the lowest scoring individual from the population. After
removing the lowest scoring individual from the population, add the
new individual to the population.
Removal of the low scoring individual can be done with function
remove-kth:
(defun remove-kth (k lst)
"Returns a list consisting of LST with the Kth element deleted."
;;; See the comments for the function replace-nth for help. The
;;; two functions are similar.
)
> (remove-kth 1 '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE))
returns: (SEATTLE SEATTLE WENATCHEE SEATTLE)
> (remove-kth 3 '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE))
returns: (SEATTLE PORTLAND SEATTLE SEATTLE)
Example of removing a "kth" individual from the population:
> (remove-kth 3 '( ((SEATTLE SEATTLE SEATTLE PORTLAND SPOKANE) . 0.84745765)
((BELLINGHAM SEATTLE SEATTLE SEATTLE SPOKANE) . 0.8583691)
((BELLINGHAM SEATTLE SEATTLE SEATTLE SPOKANE) . 0.8583691)
((SEATTLE SEATTLE SEATTLE SEATTLE SPOKANE) . 0.6097561)
((SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE) . 0) ))
Returns the following population with the 4th member (k=3) removed:
( ((SEATTLE SEATTLE SEATTLE PORTLAND SPOKANE) . 0.84745765)
((BELLINGHAM SEATTLE SEATTLE SEATTLE SPOKANE) . 0.8583691)
((BELLINGHAM SEATTLE SEATTLE SEATTLE SPOKANE) . 0.8583691)
((SEATTLE SEATTLE SEATTLE SEATTLE SEATTLE) . 0) )
6. Mutation #2
Mutate2 chooses two cities within a path and swaps them.
> (mutate2 '((SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) . 0.90909094))
This might return:
((SEATTLE WENATCHEE SEATTLE PORTLAND SEATTLE) . 0)
The example function call choses two random locations within the path,
locations 1 and 3, and swaps the two cities at that location.
This version of mutate2 does not evaluate the new individual.
An alternative version could evaluate the individual:
((SEATTLE WENATCHEE SEATTLE PORTLAND SEATTLE) . 0.90909090)
7. Writing function "crossover"
A convenient pre-defined Lisp function to use for crossover is the library
function "subseq". There are two forms of subseq:
1. (subseq lst start end) returns the portion of the list from start to end-1
2. (subseq lst start) returns the portion of the list from start to the end
Examples of the first version of subseq:
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 0 1)
(SEATTLE)
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 0 3)
(SEATTLE PORTLAND SEATTLE)
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 0 0)
NIL
Examples of the second version of subseq:
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 4)
returns: (SEATTLE)
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 1)
returns: (PORTLAND SEATTLE WENATCHEE SEATTLE)
> (subseq '(SEATTLE PORTLAND SEATTLE WENATCHEE SEATTLE) 3)
returns: (WENATCHEE SEATTLE)
Crossover works as follows:
After picking two individuals to be "crossed-over", pick a random position
and "mix and match" the two individuals at that random position.
An example using two simple lists:
(a b c d e) and (f g h i j) at position 2 results in a new
individual: (a b h i j)
The first individual is copied from 0..(2-1), it's left part.
The second individual is copied from 2..the end, it's right part.
The left part of individual 1 is appended to the right part of individual 2.
> (crossover '((WENATCHEE SEATTLE SEATTLE PORTLAND SPOKANE) . 1.459854)
'((BELLINGHAM SEATTLE SEATTLE WENATCHEE SPOKANE) . 1.4925373))
Where:2
returns: ((WENATCHEE SEATTLE SEATTLE WENATCHEE SPOKANE) . 0)
The left part of individual 1 is (WENATCHEE SEATTLE)
The right part of individual 2 is (SEATTLE WENATCHEE SPOKANE)
These two parts are appended together.
Note that in this case the chromosome strength of the new individual is:
(chromosome-strength '((WENATCHEE SEATTLE SEATTLE WENATCHEE SPOKANE) . 0))
Returns: 0.8695652
In this case, the new individual evaluated to less than the original parents.
8. Putting it all together.
The "starter" program has the following global values:
*cities* - the list of the cities in the tour:
(seattle portland spokane wenatchee bellingham)
*ncities* - the number of cities in the tour
*population* - the current population
*current-min-strength* - current minimum strength in the population
*current-pop-size* - current population size
*population-limit* - the maximum population size (set to 15)
Function "test" runs the program.
There are three optional parameters to "test":
1. The number of generations to run the test
2. The number of mutations for each generation
3. The number of crossovers for each generation
Function "test" calls the function "evolve", which is the main driver of
this genetic algorithm program.