Валиев Б.Б., Адиль А.Ж.
ИНБРИДИНГ В ГЕНЕТИЧЕСКИХ АЛГОРИТМАХ *
Аннотация:
в работе описывается структура подвида эволюционного алгоритма, а именно генетического алгоритма. Представлен процесс инбридинга с точки зрения генетического алгоритма и его влияние на популяцию алгоритма и последующие поколения
Ключевые слова:
генетический алгоритм, эволюционный алгоритм, инбридинг
УДК 004.021
Валиев Б.Б.
магистрант кафедры компьютерной инженерии
Международный университет информационных технологий
(г. Алматы, Казахстан)
Адиль А.Ж.
магистранты кафедры компьютерной инженерии
Международный университет информационных технологий
(г. Алматы, Казахстан)
ИНБРИДИНГ В ГЕНЕТИЧЕСКИХ АЛГОРИТМАХ
Аннотация: в работе описывается структура подвида эволюционного алгоритма, а именно генетического алгоритма. Представлен процесс инбридинга с точки зрения генетического алгоритма и его влияние на популяцию алгоритма и последующие поколения.
Ключевые слова: генетический алгоритм, эволюционный алгоритм, инбридинг.
Объем информации, с которым людям приходится иметь дело, удваивается каждые 12 часов [1]. Огромное количество данных, которые необходимо хранить, просматривать, изменять и удалять, требует больших усилий. По мере роста числа хранимых записей, может увеличиваться и время доступа к ним, и соответственно, падать производительность. В качестве одного из решений этой проблемы были разработаны алгоритмы, нацеленные, например, на оптимизацию запросов к базам данных. Алгоритмы, как простые наборы предопределенных инструкций, претерпели множественные изменения, породившие новый вид – генетические алгоритмы.
Генетический алгоритм
Генетический алгоритм – особый вид алгоритмов, основанный на принципах биологической эволюции, а именно на естественном отборе, наследственности и адаптивности, и ставящий в приоритет оптимизацию по некоторому заданному критерию. Генетический алгоритм работает циклично до достижения определенных условий, например, максимальная выживаемость потомка, при которой невозможно дальнейшее улучшение. Процессы, входящие в состав алгоритма, можно поделить на 5 основных групп по порядку их использования: Определение начальной популяции; Определение функции приспособленности; Выборка доступных представителей (хромосом); Скрещивание (кроссовер); Изменение потомков (мутация).
Инбридинг
В природе инбридингом считается скрещивание форм жизни, т.е. животных, растений, при котором между двумя формами существует определенная степень родства. Традиционно считается, что родственное скрещивание приводит к ослаблению потомства [2] и потере конкурентного преимущества в условиях естественного отбора, т.е. привести к инбридинговой депрессии. Однако в современном мире по этому вопросу существуют менее категоричные мнения. В некоторых работах [3] показывается, что факторы как содержание популяции, окружающая среда и т.д. оказывают влияние на уровень инбридинговой депрессии, изменяя его значение.
Классической задачей генетических алгоритмов является максимизация. Так, имеется некая начальная популяция, каждый представитель (хромосома) из которой состоит из последовательности генов (битов к примеру).
Важно отметить, чтобы последовательность генов была не в виде десятичных чисел, а в двоичной форме. Данный подход имеет большое преимущество на стадии мутации, когда проводится изменение в разрезе одного гена, например, хромосома 0011001 превращается в 0011101, где пятый ген заменяется на противоположное значение. В случае использования десятичных чисел подобные действия сильно усложняются. Конечно, существует возможность генерации случайного числа, но изменения от такой мутации слишком непредсказуемы. Обратимся к предыдущему примеру хромосомы 0011001, у которой мутирует один ген. Допустимые решения: {1011001, 0111001, 0001001, 0010001, 0011101, 0011011, 0011000}. При представлении совокупности генов каждой хромосомы как одно число, из числа 25 можно получить {89, 57, 9, 17, 29, 27, 24}. Генерация случайного числа может привести к любому числу, которое по теории вероятности, может оказаться максимально далеко от допустимых решений. Вероятность удачного попадания регулируется лишь размером выборки, из которой выбирается случайное число. На основе этого, представление хромосом в двоичном виде предпочтительно.
Несмотря на преимущественно негативную ассоциацию инбридинга в природе, в данной статье выдвигается гипотеза, что инбридинг может оказаться полезной в условиях использования генетического алгоритма.
Генетический алгоритм, равно как и другие виды эволюционных алгоритмов, нацелен на нахождение решения, удовлетворяющего исходной задаче. При этом следует отметить, что поиск наилучшего решения может занимать неоправданно длительное время, что может свести к минимуму полезность такого подхода. В этой связи, во внутренней логике алгоритма должно присутствовать ограничение, которое приведет алгоритм к остановке при достижении определенных лимитов, таких как максимальное количество циклов алгоритма, временное ограничение, малый прирост качества результатов в нескольких последующих поколениях решений и т.д.
Определение начальной популяции
Для работы алгоритма требуется определенная начальная выборка данных, т.е. популяция, с которой будут производиться дальнейшие операции. Каждый отдельный объект в этой популяции является своего рода решением. Это решение необязательно оптимально. Оно, так же, как и вся популяция, могло быть сгенерировано случайно либо внесено в алгоритм из определенного источника. Каждый отдельный представитель популяции называется хромосомой. Структура хромосомы, т.е. решения, включает в себя составляющие этого решения. Запись этой структуры производится по-разному, исходя из начальных мотивов использования алгоритма. В нашем же случае выбирается тип кодировки, который позволит записывать хромосомы и гены по некому общему формату. Предположим, что значение 127 – максимально возможное число в подборке. В двоичном формате оно записывается как 1111111. При переводе другого числа в двоичный формат, например числа 28, его двоичная форма должна быть той же длины, что у предыдущего числа. Соответственно, двоичная форма числа 28 – 0011100.
При условии, что хромосомы записываются в десятичном виде, модификация этих значений упускала бы определенные моменты логики, нежели при записи в двоичном виде. Например, число 2 в двоичном виде с тремя битами обретает вид 010. При наличии правила, по которому треть хромосомы должна быть изменена, при небольшой модификации одного бита значение 010 может измениться в 110, к примеру. В двоичном формате изменился лишь один бит и это изменение имеет логику, чего нельзя сказать о десятичном виде, так как это же значение будет равно 5.
К тому же изменить ту же треть от цифры 5 логически труднее, нежели менять последовательность битов. В этой связи использование двоичного формата более предпочтительно с точки зрения генетического алгоритма.
Определение функции приспособленности
Функция приспособленности является ключевым звеном в определении насколько хорошей является отдельное решение, т.е. хромосома. Определение данной функции является одним из самых сложных процессов в построении алгоритма, так как необходимо понимание предпочтительного конечного результата и путей его достижения. Например, пример максимизации функции сводится к тому, чтобы функция включала все составляющие хромосомы – гены и стремилась нарастить их. Однако в более сложных случаях может требоваться как увеличение одних параметров, так и уменьшение других.
Выборка доступных хромосом
На данной стадии происходит выбор хромосом, которые создадут новое поколение в популяции. Выбор осуществляется исходя из того, насколько хорошо хромосома соответствует функции приспособленности. Чем больше хромосома соответствует функции, тем больше ее шансы быть выбранной. Однако эта вероятность не гарантирует выбор наиболее подходящего кандидата, а лишь сильно увеличивает его. Такой подход обеспечивает определенное разнообразие в популяции, давая небольшую возможность перехода неоптимальных генов в следующие поколения. На стадии выборки необходимо выбрать несколько хромосом для создания пары. Пара может включать как две, так и большее количество хромосом. Это одно из особенностей алгоритма, отличающее его от природных процессов, где максимальное количество родителей равно двум
Скрещивание
Скрещивание происходит по принципу разделения последовательности генов обоих хромосом, которые станут будущими родителями. Разделение происходит на определенном отрезке или отрезках в зависимости от желаемого уровня перемешивания. Далее разделенные фрагменты обмениваются между родителями, образуя новые хромосомы. Например, первая хромосома – 111111, вторая – 000000. При разделении после 2 и 4 бита, мы получим две новые хромосомы, которые будут иметь признаки обоих родителей, но будут отличны от них. Результатом этого скрещивания станет 110011 и 001100. Этот механизм важен для получения хромосом, которые имеют общее с существующими хромосомами, но при этом могут привести к более качественному решению проблемы.
Мутация
Мутацией называется процесс небольшого изменения получаемых хромосом. На практике уровень мутации редко превышает порог в 10% [4]. Мутация также добавляет новые признаки. Однако примечательно в ней то, что в отличии от скрещивания, в мутации создаются признаки, которых могло не быть ни у кого из родителей. Этот процесс также добавляет уникальность в популяцию, увеличивая ее разнообразность.
Инбридинг
Основной процесс, которого касается инбридинг – выборка. Целью выборки при нормальных обстоятельствах является отбор наилучших хромосом с точки зрения целевой функции. Следует отметить, что выборка склоняется к выбору более сильных хромосом, нежели слабых. Это приводит к тому, что представители слабых генов в классическом случае имеют меньше шансов на выживание. Так как инбридинг включает в себя скрещивание близкородственных хромосом, выбор двух слабых родственников для продолжения рода имеет очень низкую вероятность, которая будет еще больше уменьшаться с каждым поколением.
Противоположным случаем является инбридинг сильных хромосом. Как было отмечено ранее, сильное соответствие функции полезности приводит к большей вероятности выбора хромосомы. Хромосомы не ограничены становлением родителем лишь однажды в рамках одного цикла, т.е. одна и та же хромосома может быть выбрана родителем несколько раз. Это приводит к увеличению ее присутствия в популяции. Конечно, можно сдерживать прирост генов этой хромосомы в популяции, предоставляя возможность роста популяции. При условии, что размер популяции ограничен, даже с запасом расширения (например, предполагается будущее увеличение популяции с 100 хромосом до 500, но это число тем не менее ограничено) популяция достигнет предела, после которого не сможет сдерживать рост процентного соотношения генов. В итоге сильные гены исходной хромосомы вытеснят все другие гены из популяции, приведя к состоянию, когда все решения оставшиеся являются одинаковыми, так как все исходят из одного предшественника. Даже учитывая мутацию, которая будет приводить к изменению определенной доли хромосом, этих изменений будет недостаточно для изменения общей ситуации в популяции, так как эти изменения будут считаться ухудшающими показатели хромосомы и алгоритм будет противодействовать их передаче следующим поколениям, тем самым выбирая немутировавшие хромосомы, которые однако уникальности не имеют по причине полной схожести с другими хромосомами.
Данная ситуация именуется конвергенцией – достижением состояния популяции, при котором все представители похожи друг на друга. Скрещивание этих представителей не привносит в популяцию отличительные черты из-за схожести скрещиваемых. Конвергенция приводит к нахождению локального оптимума, т.е. найденное решение хорошо в пределах текущих решений. Однако оно может быть хуже отдаленного решения, до которого нельзя добраться, скрещивая имеющиеся хромосомы. Решением является увеличение процента мутации, которое будет способно перекрыть превосходящее число инбридинговой популяции, приводя к появлению утерянной уникальности.
Заключение
Таким образом инбридинг в генетическом алгоритме имеет много общего с природным инбридингом. Однако в среде алгоритма есть возможность его ослабления путем усиления мутации. Инбридинг хорош в том случае, если начальные хромосомы, выбранные для инбридинга, достаточно хорошо соответствуют функции приспособленности, тем самым увеличивая присутствие хороших генов. Таким образом гипотеза была доказана. При выборе слабых хромосом линия инбридинга будет вытеснена более сильными конкурентами в рамках популяции.
СПИСОК ЛИТЕРАТУРЫ:
David Russell Schilling, “Knowledge Doubling Every 12 Months, Soon to Be Every 12 Hours.” IndustryTap – 2013 [Электронный ресурс]. URL: https://www.industrytap.com/knowledge-doubling-every-12-months-soon-to-be-every-12-hours/3950 (дата обращения: 22.03.2022).
Charlesworth D., Willis J. H. The genetics of inbreeding depression //Nature reviews genetics. – 2009. – Т. 10. – №. 11. – С. 783-796.
Keller L. F., Waller D. M. Inbreeding effects in wild populations //Trends in ecology & evolution. – 2002. – Т. 17. – №. 5. – С. 230-241.
Piszcz A., Soule T. Genetic Programming: Analysis of Optimal Mutation Rates in a Problem with Varying Difficulty //FLAIRS Conference. – 2006. – С. 451-456.
Valiev B.B.
Master's student of Computer Engineering Department
International University of Information Technologies
(Almaty, Kazakhstan)
Adil A.Zh.
Undergraduates of the Department of Computer Engineering
International University of Information Technologies
(Almaty, Kazakhstan)
INBREEDING IN GENETIC ALGORITHMS
Abstract: the paper describes the structure of a subspecies of an evolutionary algorithm, namely a genetic algorithm. The process of inbreeding from the point of view of the genetic algorithm and its impact on the population of the algorithm and subsequent generations is presented.
Keywords: genetic algorithm, evolutionary algorithm, inbreeding.
Номер журнала Вестник науки №5 (50) том 3
Ссылка для цитирования:
Валиев Б.Б., Адиль А.Ж. ИНБРИДИНГ В ГЕНЕТИЧЕСКИХ АЛГОРИТМАХ // Вестник науки №5 (50) том 3. С. 115 - 122. 2022 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/5620 (дата обращения: 30.04.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2022. 16+