назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [ 134 ] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


134

Глава 13 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

Рассматрим основную идею построения так называемых генетических алгоритмов. Этот класс алгоритмов относится к так называемым эвристическим алгоритмам. Эвристические алгоритмы - это итерационные методы решения оптимизационных задач, которые приводят

Генетические алгоритмы относятся к эвристическим алгоритмам, то есть являются итерационными методами решения оптимизационных задач, которые приводят, вообще говоря, не к оптимальному, но, как правило, к близкому к оптимальному решению.

не к оптимальному, но, как правило, к и близкому к оптимальному решению. Правомочность таких алгоритмов имеет не строго математическое, а лишь интуитивное обоснование. Они обычно применяются в тех случаях, когда использование точных оптимизационных алгоритмов на практике невозможно. Приводятся примеры успешного применения генетических алгоритмов.

13.1. Естественный отбор в природе

Эволюционная теория утверждает, что каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. В процессе эволюции многие виды насекомых и рыб приобрели защитную окраску, еж стал неуязвимым благодаря иглам, человек стал обладателем сложнейшей нервной системы. Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Рассмотрим, какими же средствами природа решает эту задачу оптимизации.

Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После



смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает.

Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (дезоксирибонуклеиновая кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых Л, Г, С и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума- это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой; такое образование называется хромосомой.

Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т.д.) кодируется определенной частью хромосомы, которая называется геном этого свойства. Например, ген цвета глаз содержит информацию, кодирующую определенный цвет глаз. Различные значения гена называются его аллелями.

При размножении животных происходит слияние двух родительских половых клеток, и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия- кроссовер {cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.

При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они скорее всего сохранятся в данном виде, при этом произойдет скачкообразное повышение приспособленности вида.

13.2. Что такое генетический алгоритм

Генетический алгоритм имитирует эволюцию популяции как циклический про-

Пусть дана некоторая сложная функция {целевая функция), зависящая от нескольких переменных, и требуется цесс скрещивания индиви- 11 . значения переменных, при дуумов и смены поколений.г» г

которых значение функции максимально. Задачи такого рода называются задачами оптимизации и встречаются на практике очень часто. 410



Один из наиболее наглядных примеров - задача распределения инвестиций. В этой задаче переменными являются объемы инвестиций в каждый проект, а функцией, которую нужно максимизировать- суммарный доход инвестора. Также даны значения минимального и максимального объема вложения в каждый из проектов, которые задают область изменения каждой из переменных.

Попытаемся решить эту задачу, применяя известные нам природные способы оптимизации. Будем рассматривать каждый вариант инвестирования (набор значений переменных) как индивидуума, а доходность этого варианта - как приспособленность этого индивидуума. Тогда в процессе эволюции (если мы сумеем его организовать) приспособленность индивидуумов будет возрастать, а значит будут появляться все более и более доходные варианты инвестирования. Остановив эволюцию в некоторый момент и выбрав самого лучшего индивидуума, мы получим достаточно хорошее решение задачи.

Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.

Вот как моделируется генетическое наследование (табл. 13,1):

Таблица 13.1

Жизненный цикл популяции -это несколько случайных скрещиваний (посредством кроссовера) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов.

Отбор в генетическом алгоритме - это процесс формирования новой популяции из старой, после чего старая популяция погибает.

Хромосома

Вектор (последовательность) из нулей и единиц. Каждая позиция (бит) называется геном

Индивидуум = = генетический код

Набор хромосом = вариант решения задачи

Кроссовер

Операция, при которой две хромосомы обмениваются своими частями

Мутация

Случайное изменение одной или нескольких позиций в хромосоме

Чтобы смоделировать эволюционный процесс, сгенерируем вначале случайную популяцию - несколько индивидуумов со случайным набором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [ 134 ] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]