Введение, История - Генетический алгоритм
Генетимческий алгоримтм (англ.Genetic algorithm ) -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическуюэволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора "скрещивания", который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Генетический алгоритм популяция тривиальный
История
"Отцом-основателем" генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого "Адаптация в естественных и искусственных системах" (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.
Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов. Примерно через десять лет появились первые теоретические обоснования этого подхода. На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.
Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:
Www. natural-selection. com/eps/
Mat. gsia. cmu. edu/Conferences/ .
Общую схему генетических алгоритмов проще всего понять, рассматривая задачи безусловной оптимизации
Max{ f (i) | i {0,1}n }.
Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной Популяции I 0 = {I 1 ,I 2, ...,Is } -- конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.
На каждом шаге эволюции с помощью вероятностного оператора СелекцииВыбираются два решения, родители I 1, I 2. Оператор Скрещивания По решениям I 1, I2 строит новое решение I' , которое затем подвергается небольшим случайным модификациям, которые принято называть Мутациями . Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.
Доказательство теоремы схем.
1. Выбрать начальную популяцию I 0иположить
F* = max{F (I )| I I 0}, K : = 0.
- 2. Пока не выполнен критерий остановки делать следующее. 2.1. Выбрать родителей I 1, I 2 из популяции Ik . 2.2. Построить I' по I 1, I 2 . 2.3. Модифицировать I' . 2.4. Если F * < F (I ' ), то F * : = F (I ' ). 2.5. Обновить популяцию и положитьK : =K+1 .
Гипотеза 1.
В среднем локальные оптимумы расположены гораздо ближе к глобальному оптимуму, чем к случайно выбранной точке. Их распределение в области допустимых решений на является равномерным. Они концентрируются в районе глобального оптимума, занимая область небольшого диаметра.
Эта гипотеза отчасти объясняет работоспособность генетических алгоритмов. Если в популяции собираются локальные оптимумы, которые согласно гипотезе сконцентрированы в одном месте, и очередное решение I' Выбирается где-то между двумя произвольными локальными оптимумами, то такой процесс имеет много шансов найти глобальный оптимум. Аналогичные рассуждения объясняют работоспособность и других локальных алгоритмов. В связи с этим проверка и теоретическое обоснование данной гипотезы представляет несомненный интерес.
Похожие статьи
-
В историческом плане вопрос об эволюции генов является важнейшим, поскольку эволюция генов связана с истоками жизни вообще и ее совершенствованием в...
-
Введение - Молекулярная и генетическая организация плазмид
Плазмиды - внехромосомные генетические элементы, способные к автономному поддержанию в цитоплазме бактерий или существованию в нтегрированном в хромосому...
-
Введение, История открытия - Витамин Н, биотин
В составе пищи, которую мы едим, содержаться различные вещества, необходимые для нормальной работы всех органов, способствующие укреплению организма,...
-
Введение, Открытие витаминов - История развития учения о витаминах
Ко второй половине XIX столетия было установлено, что пищевая ценность продуктов питания определяется содержанием в них белков, жиров, углеводов,...
-
Введение - Отражение истории формирования фармацевтических знаний в музейных коллекциях
Большой интерес представляют китайская медицина и фармация. Собственная научная медицина и фармация возникли в Китае примерно за 1000 лет до нашей эры....
-
Введение - История развития представлений о биосфере
Биосфера -- населенная жизнью оболочка Земли, состав, структура и энергетика которой в существенных чертах обусловлены прошлой или современной...
-
История исследования плазмид - Молекулярная и генетическая организация плазмид
Начало исследования плазмид относят к 20 гг. XX века. В 1921 г. Bourdet и Ciuca открыли лизогенные бактерии, способные спонтанно лизироваться. В 1925 г....
-
Введение, Краткая история учения о биологическом окислении - Биологическое окисление
Биологическое окисление - это совокупность окислительных процессов, протекающих в живых организмах. Биологическое окисление выполняет ряд важных Функций...
-
1. Внутрикожная инъекция. 2. Подкожная инъекция. 3. Внутримышечная инъекция. 4. Внутривенная инъекция. 5. Внутривенное капельное вливание с помощью...
-
Введение, Анатомия в Древней Руси - История развития отечественной анатомии
Анатомия человека - наука, изучающая форму и строение тела человека в связи с его функциями и закономерностями развития. Изучая строение отдельных...
-
Введение - Мобильные генетические элементы эукариот: транспозоны и ретротранспозоны
В начале 1950_х гг. Б. Мак-Клинток на основе генетических экспериментов, выполненных на кукурузе, постулировала наличие в геноме высших эукариот...
-
Введение - Особенности генетического аппарата вирусов
Цель: изучение генетического материала внеклеточных организмов. Задания: 1. Многоуровневая организация генома. 2. Геном РНК - вирусов. В настоящее время...
-
Введение - Биосинтез белков. Ген и его роль в синтезе белков
Способность клеток поддерживать высокую упорядоченность своей организации в хаотичной Вселенной зависит от генетической информации, которая реализуется,...
-
Введение, История возникновения - Местные анестетики
Анестетики -- лекарственные средства, обладающие способностью вызывать анестезию. Местные анестетики обратимо снижают возбудимость чувствительных нервных...
-
Введение - Характеристика пестицидных белков Bacillus thuringiensis и их генетических детерминант
Объектом данной курсовой работы является Bacillus thuringiensis , а предметом - использование данного вида эубактерий как продуцента хозяйственно...
-
Введение, История возникновения талассотерапии - Талассотерапия
Целебные свойства природы известны человечеству с древнейших времен. В античных государствах Греции и Рима существовали курорты, использовавшие целебный...
-
Введение - История анатомии человека
Предметом изучения анатомии человека являются форма и строение, происхождение и развитие человеческого организма. Анатомия человека -- одна из...
-
Введение, История появления раздельного питания - Раздельное питание. Преимущества и недостатки
Еда - существенная часть сбалансированной диеты". Фран Лебовиц Сейчас раздельным питанием увлекаются очень многие. Кто-то таким образом пытается...
-
Генетический дрейф - Генетические процессы в популяциях
Изучение природных популяций показывает, что, как правило, они не представляют собой единой панмиксной единицы. Подразделенность большой популяции на...
-
Популяционная генетика - Генетические процессы в популяциях
Популяция (позднелат. populatio, от лат. populus -- народ, население) это совокупность особей одного вида, более или менее длительно занимающая...
-
Генетический скрининг взрослых - Геном человека
В настоящее время нет общенациональных программ генетического скрининга взрослого населения, но некоторые достижения заслуживают упоминания. Лучшим...
-
Механизм, благодаря которому генетическая информация ДНК "транскрибируется" в матричную РНК, а затем транслируется в белок, выяснился через несколько лет...
-
Введение - Популяция как элементарная единица эволюции
Все виды живых организмов в природе представлены совокупностями особей - популяциями. Популяции - такие же природные реальности, как клетки с кодами их...
-
Введение в биологию - Введение в физиологию
Биология (от греч. bios-жизнь, logos-понятие, учение) - это наука, изучающая живые организмы. Развитие этой науки шло по пути последовательного упрощения...
-
Направления эволюции, Генетические и онтогенетические основы эволюции - Механизмы эволюции
Направление эволюции каждой систематической группы определяется взаимоотношениями между особенностями среды, в которой протекает эволюция данного...
-
Вирусы как независимые генетические системы Какое место занимают вирусы в биологическом мире? Каково их происхождение и кто их ближайшие родственники?...
-
Присутствие мобильных элементов в геноме является необходимым для генерирования генетического разнообразия посредством гомологической рекомбинации в...
-
Общая информация о развитии биосферы - История развития представлений о биосфере
Возраст Земли, определяемый методами изотопной геологии, составляет около 5 млрд лет. Наиболее принятые показатели 4,6-4,7 млрд лет. Приблизительно таков...
-
Рассмотрение идеи глобального эволюционизма имеет своей первоочередной задачей ликвидацию разрывов между разными областями бытия. Поэтому внимание...
-
Введение, Эпигенетика. Что такое эпигенетическая изменчивость - Эпигенетическая изменчивость
В геноме человека содержится около 25 тыс. генов, но одновременно в клетке любой живой ткани работает не более половины всех генов. Часть из них нужна...
-
Конституциология и современная биомедицинская антропология - Введение в конституциологию
Наряду с самыми различными аспектами Изменчивости человека существует еще один: внутри любой человеческой популяции можно найти людей высоких и низких,...
-
Генетический код - Великие открытия в генетике ХХ века
РНК передает инструкции от ДНК для создания белка. Но каков генетический код - последовательность инструкций, которая делать этот процесс возможным? В...
-
Эволюционная биология. История эволюционного учения - Биология как естественная наука
Эволюционная биология - раздел биологии, изучающий происхождение видов от общих предков, наследственность и изменчивость их признаков, размножение и...
-
Введение, Что такое микробиология? - Достижения и открытия ученых микробиологов нашей страны
Микробиология ученый открытие эмпирический Микробиология прошла длительный путь развития, исчисляющийся многими тысячелетиями. Уже в V. VI тысячелетии до...
-
Введение - Современная теория эволюции
Эволюция происходит в течение периода времени, превышающего срок жизни одного поколения, и заключается в изменении наследуемых черт организма. Первым...
-
Введение - Методология и методы естественнонаучного познания
Движение мысли от незнания к знанию руководствуется методологией. Методология -- философское учение о методах познания и преобразования действительности,...
-
Введение - Характеристика регуляции гемопоэза
Кровь представляет собой разновидность соединительной ткани. Она непрерывно движется по кровеносным сосудам. Движение крови поддерживается...
-
Морская свинка обладает 32-мя парами хромосом. Таким образом получаем что общее число хромосом у морской свинки 64 шт о своему генотипу морские свинки...
-
Введение - Научная картина мира
Представления о свойствах и закономерностях окружающей нас природы возникают на основе тех знаний, которые в каждый исторический период дают конкретные...
-
Факторы популяционной динамики, Инбридинг - Генетические процессы в популяциях
Инбридинг Понятие "инбридинг" широко используется в популяционной генетике при описании особенностей генетической структуры популяций. Случайное...
Введение, История - Генетический алгоритм