Genetic Algorithm for Emacs

This package provides some functions which enable you to run genetic algorithm in Emacs.

Dependency

This package depends on dash.el. Please get it from here.

How to Use?

You can use egalgo-run for running genetic algorithm.

(defvar goods
  ;; (Volume . Value)
  '((3 . 4)
    (2 . 1)
    (6 . 3)
    (6 . 2)
    (2 . 6)
    (7 . 5)
    (5 . 5)
    (5 . 9)
    (2 . 3)
    (4 . 5)))

(defvar knapsack-size 10)

(defun knapsack-rater (chromosome)
  (let ((value 0)
        (volume 0))
    (dotimes (i (length chromosome))
      (when (nth i chromosome)
        (setq volume (+ volume (car (nth i goods))))
        (setq value  (+ value  (cdr (nth i goods))))))

    (if (<= volume knapsack-size)
        value
      0)))

;; Minimum running.
(plist-get                              ;Get result from returned value
 (egalgo-run
  '(t t t t t t t t t t)                ;t means boolean gene.
  #'knapsack-rater)
 :max-rate)                             ;rate of best chromosome.

;; You can get best chromosomes
(car                       ;if you need only one of them, use car.
 (plist-get egalgo-latest  ;You can also access latest result like this.
  :max-chromosomes))       ;list of best chromosomes.

;; Additional running.
(egalgo-run
 '(t t t t t t t t t t)                 ;t means boolean gene.
 #'knapsack-rater
 :size 50             ;Size of each generation.
 :crossover 0.8       ;Probability of doing crossover.
 :mutation 0.05       ;Probability of each gene mutating.
 :n-point-crossover 2 ;means 2 point crossover. `t' means unicrossover.
 :termination 200     ;Number of maximum generation.
 )

(egalgo-run
 '(t t t t t t t t t t)                 ;t means boolean gene.
 #'knapsack-rater
 :termination 100
 :size 30
 :elite 1                               ;keep 1 elite chromossomes
 :mutation 0.01
 :n-point-crossover t)                  ;means unicrossover

(egalgo-run
 '(t t t t t t t t t t)
 #'knapsack-rater
 ;; termination can be function.
 :termination
 (lambda (stack-of-rates _generation)
   (or
    (not (nth 1 stack-of-rates))
    (< 10 (abs (- (-sum (nth 0 stack-of-rates))
                  (-sum (nth 1 stack-of-rates))))))))

Returned value of egalgo-run

egalgo-run returns plist. This have at least 2 elements.

• :chromosomes: list of all chromosomes of last generation.
• :rates: list of rates of all chromosomes of last generation.
• :rates-log: list of list of rates of all chromosomes of each generation. Latest rates are in the first of this list.
• :max-rate: maximum rate of latest chromosomes’ rates.
• :generation: the number of total generations.
• :chromosomes-log: list of list of chromosomes of each generation. Latest chromosomes are in the first of this list. This is valid only when the argument log is non-nil.
• :max-chromosomes: list of chromosomes rated maximum rate.

You can get these value by using plist-get. Use like (plist-get result-of-egalgo-run :chromosomes)

In addition, egalgo-latest have result of latest egalgo-run.

Arguments of egalgo-run

First and second argument (chromosome-definition and rater) are necessary, and other argument is optional. Optional arguments are keyword arguments, such as :size 100.

chromosome-definition

This is the first argument, and the value should be list. Each element expresses each gene. Each element should be:

• t
• vector which has 2 elements
• list
• positive integer

t

Means boolean gene. On the genetic locus, there is t or nil in chromosomes.

;; This function generate chromosome from chromosome-definition.
(egalgo--generate-chromosomes-from-definition
 '(t t t) 3)
;;=> ((t nil t) (nil t nil) (nil t t))

Vector which has 2 elements

Means spreaded and continuous gene. For example, on the genetic locus of [3 5], there is decimal value from 3 to 5 in chromosomes.

;; This function generate chromosome from chromosome-definition.
(egalgo--generate-chromosomes-from-definition
   '([3 5] [-1 2] [1.5 2] [0 3]) 3)
  ;;=> ((4.803373336791992 0.9197903871536255 1.655701458454132 1.557612419128418)
  ;;    (3.428975820541382 0.6926283836364746 1.926502287387848 1.897337794303894)
  ;;    (4.929042339324951 0.9992145299911499 1.5691171288490295 0.10083675384521484))

list

Means discrete gene. For example, on genetic locus of (1 3 5 foo), there is 1, 3, 5 or symbol foo in chromosomes.

;; This function generate chromosome from chromosome-definition.
(egalgo--generate-chromosomes-from-definition
 '((1 3 5 foo) (2 4 6 bar) (ww 3 2.3 0)) 3)
;;=> ((1 2 ww) (1 4 0) (foo bar 3))

positive integer

Also means discrete gene. If the number is n, gene on the genetic locus can be integer which is 0 or more, and less than n. For example, 5 is same as (0 1 2 3 4) on chromosome-definition.

;; This function generate chromosome from chromosome-definition.
(egalgo--generate-chromosomes-from-definition
 '(5 3 2) 3)
;;=> ((0 0 0) (0 0 1) (4 2 1))

;; Same as below
(egalgo--generate-chromosomes-from-definition
 '((0 1 2 3 4) (0 1 2) (0 1)) 3)
;;=> ((2 1 0) (3 1 1) (1 2 0))

rater

rater should be a function which takes 1 argument, and returns non-negative integer or decimal. The argument is chromosome, which is defined by chromosome-definition. Returned value is rate of the chromosome passed as the argument.

size (optional, keyword)

The number of chromosomes in each generation. It should be positive integer. Default value is 100.

crossover (optional, keyword)

Probability of crossovering 2 chromosomes. If determine DO crossover, then select 2 chromosomes, and crossover them. If not, Select 1 chromosome and push it to next generation.

This should be non-negative decimal which is 1 or less. Default value is 0.9.

mutation (optional, keyword)

Probability of each gene being mutated.

This should be non-negative decimal which is 1 or less. Default value is 0.01.

n-point-crossover (optional, keyword)

Number of times crossovering per 1 crossovering process. If the value is t, it means unicrossover.

This should be positive integer or t.

selector (optional, keyword)

Function which selects chromosomes used to crossover or take over. This function should:

• take 1 argument, which is list of rate of each chromosome
• return index of selected chromosome
• NOT select the chromosome whose rate is nil

This can be alias, which is defined in egalgo-selector-alias.

Default value is roulette, which means roulette selector.

termination (optional, keyword)

termination is the number of maximum generation, or function which determine to termination the algorithm or not. If number, finish algorithm when generation become the value. If function, continue algorithm when the function returns non-nil. The function take 2 arguments, stack list of rates of all generation and generation number. First element of the stack list is rates (list of rate of each chromosome) of latest generation, for example.

Default value is 1000.

log (optional, keyword)

If t, plist returned by egalgo-run has value keyed by :chromosomes-log. This is stack list of chromosomes of each generation. car of it is same as chromosomes of last generation.

Default value is nil.

elite (optional, keyword)

The number of elite chromosomes, which absolutely stays until next generation.

Default value is 0.

show-rates (optional, keyword)

If the value is t, display rates of chromosomes of each generation.

Default value is nil.

License

This package is licensed by GPLv3. See LICENSE.