Методы скрещивания в генетическом алгоритме. Точечный, двухточечный и равномерный кроссоверы. Реализация на Python

January 30, 2019 16:15

Операция скрещивания в генетических алгоритмах - это точечное скрещивание. Существует несколько видов точечного скрещивания: одноточечное, двухточечное и равномерное. В реализации программы представлены все 3 метода.

Общий принцип работы: выбирается пара хромосом из родительской популяции; затем рандомно выбираются точки скрещивания; в результате скрещивания получается два потомка. 

Одноточечное скрещивание: выбирается пара хромосом; рандомно (случайно) выбирается точка скрещивания; в результате скрещивания получаются две пары, их мы покажем наглядно в примере ниже.

Пример:
A: 12341234
B: 56785678
Точка разбиения: 3.

Покажем наглядно точку:
A: 123|41234
B: 567|85678

Результат скрещивания:
A`: 123|85678 (12385678)
B`: 567|41234 (56741234)

Двухточечное скрещивание: работает по тому же принципу, что и одноточечное, за исключением того, что выбирается две рандомных точки и хромосомы обмениваются между собой этим участком; подробнее в примере.

Пример:
A: 00000000
B: 11111111
Точки разбиения: 3, 5.

Показ точек разбиения:
A: 000|00|000
B: 111|11|111

Результат скрещивания:
A`: 00011000
B`: 11100111

Равномерное скрещивание: для каждой хромосомы из пары случайно выбирается число 0 или 1, где 0, например, будет означать четность, а 1 - нечетность; в соответствии с выбранным числом меняются значения четных или нечетных позиций в хромосоме А на значения хромосомы Б; подробнее в примере ниже.

Пример:
A: 12345678
B: abcdefgh

Случайные числа: 0 (четное), 1 (нечетное).

Результат кроссовера:
A`: 1b3d5f7h
B`: a2c4e6g8

В приведенных примерах счет символов в строках начинается с 1.

Реализация на Python:

from random import choice
from string import ascii_letters, digits
from sys import argv

def single_point(male, female, a):
    return male[:a] + ['|'] + female[a:]

def double_point(male, female, a, b):
    return male[:a] + ['|'] + female[a:b] + ['|'] + male[b:]

def single_point_r(male, female, a):
    return female[:a] + ['|'] + male[a:]

def double_point_r(male, female, a, b):
    return female[:a] + ['|'] + male[a:b] + ['|'] + female[b:]

def uniform_cross(male, female, a):
    return [male[i] if i % 2 == 0 else female[i] for i in range(len(male))]

def uniform_cross_rev(male, female, a):
    return [male[i] if i % 2 == 1 else female[i] for i in range(len(male))]

# def new_person(length): 
#     return [choice(ascii_letters + digits) for i in range(length)]

# male, female = new_person(int(argv[1])), new_person(int(argv[1]))

def new_person(length): 
    return [choice(ascii_letters) for i in range(length)]

def new_person_digits(length):
    return [choice(digits) for i in range(length)]

female = new_person(int(argv[1]))
male = new_person_digits(int(argv[1]))

print(
    f'Male:         {"".join(male)}',
    f'Female:       {"".join(female)}',
    f'', 
    f'Single 1:       {"".join(single_point(male, female, int(argv[2])))}',# argv2 - одноточечный
    f'Single 2:       {"".join(single_point_r(male, female, int(argv[2])))}',# argv2 - одноточечный
    f'', 
    f'Double 1:       {"".join(double_point(male, female, int(argv[3]), int(argv[4])))}',# 3-4 двуточечн
    f'Double 2:       {"".join(double_point_r(male, female, int(argv[3]), int(argv[4])))}',# 3-4 двуточечн
    f'', 
    f'Ravnomern A:      {"".join(uniform_cross(male, female, int(0)))}',# 5 - равномерн
    f'Ravnomern B:      {"".join(uniform_cross_rev(male, female, int(0)))}',
    sep='\n')