Эволюционные методы и вычисления

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

• Введение
• 1. Простой генетический алгоритм
• 1.1 Выбор родителей
• 1.2 Кроссинговер
• 1.3 Мутация
• 1.4 Селекция
• 2. Применение генетического алгоритма
• 3. Реализация простого генетического алгоритма в MATLAB
• Список литературы
• Введение
• Природа поражает своей сложностью и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.[3]
• Эволюционные методы являются приближенными методами решения задач оптимизации и структурного синтеза. Большинство эволюционных методов основано на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению.
• Эволюционные вычисления составляют один из разделов искусственного интеллекта. При построении систем искусственного интеллекта по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, например, это может быть и нейронная сеть и набор логических правил. К основным эволюционным методам относятся методы отжига, генетические, поведения "толпы" (PSO), колонии муравьев (ACO), генетического программирования.
• В отличие от точных методов математического программирования эволюционные методы позволяют находить решения, близкие к оптимальным, за приемлемое время, а в отличие от других эвристических методов оптимизации характеризуются существенно меньшей зависимостью от особенностей приложения (т.е. более универсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оптимальному решению. Универсальность эволюционных методов определяется также применимостью к задачам с неметризуемым пространством управляемых переменных (т.е. среди управляемых переменных могут быть и лингвистические величины, т.е. не имеющие количественного выражения).
• В методе отжига (Simulated Annealing) имитируется процесс минимизации потенциальной энергии тела во время отжига деталей. В текущей точке поиска происходит изменение некоторых управляемых параметров. Новая точка принимается всегда при улучшении целевой функции и лишь с некоторой вероятностью при ее ухудшении.
• Важнейшим частным случаем эволюционных методов являются генетические методы и алгоритмы. Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.
• Свойства объектов представлены значениями параметров, объединяемых в запись, называемую в эволюционном методе хромосомой. В генетическом алгоритме оперируют подмножеством хромосом, называемом популяцией. Имитация генетических принципов -- вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции -- ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению.
• Среди эволюционных методов находят применение также методы, которые в отличие от генетического алгоритма оперируют не множеством хромосом, а единственной хромосомой. Так, метод дискретного локального поиска (его англоязычное название Hillclimbing) основан на случайном изменении отдельных параметров (т.е. значений полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют мутациями. После очередной мутации оценивают значение функции полезности (Fitness Function) и результат мутации сохраняется в хромосоме только, если улучшилась. При "моделировании отжига" результат мутации сохраняется с некоторой вероятностью, зависящей от полученного значения .
• В методе PSO (Particles Swarm Optimization) имитируется поведение множества агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента.
• Метод колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих длину своих маршрутов на пути от муравьиной кучи до источника пищи.[1]
• 1. Простой генетический алгоритм
• Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, генетические алгоритмы могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.
• Основные принципы генетических алгоритмов были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличии от эволюции, происходящей в природе, генетические алгоритмы только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.
• В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за привлечение брачного партнера. Те особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов воспроизвести потомков. Слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространятся в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению "суперприспособленного" потомка, чья приспособленность больше, чем приспособленность любого из его родителя. Таким образом, вид развивается, лучше и лучше приспосабливаясь к среде обитания.
• Генетические алгоритмы используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность "воспроизводит" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.
• Так и воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи.[3]
• Для применения генетического алгоритма необходимо:
• 1. выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его полезность, т.е. выделить множество управляемых параметров
• среди могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин (enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;
• 2. сформулировать количественную оценку полезности вариантов объекта -- функцию полезности . Если в исходном виде задача многокритериальна, то такая формулировка означает выбор скалярного (обобщенного) критерия;
• 3. разработать математическую модель объекта, представляющую собой алгоритм вычисления для заданного вектора ;
• 4. представить вектор в форме хромосомы -- записи следующего вида (см. рис. 1).
• 5.
• Рис. 1. Хромосома
• В генетическом алгоритме используется такая терминология:
• · ген -- управляемый параметр ;
• · аллель -- значение гена;
• · локус (позиция) -- позиция, занимаемая геном в хромосоме;
• · генотип -- экземпляр хромосомы, генотип представляет совокупность внутренних параметров проектируемого с помощью генетического алгоритма объекта;
• · генофонд -- множество всех возможных генотипов;
• · функция полезности (приспособленности) -- целевая функция;
• · фенотип -- совокупность значений критериев, получаемых после декодирования хромосомы, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью генетического алгоритма объекта.
• Вычислительный процесс начинается с генерации исходного поколения -- множества, включающего хромосом, -- размер популяции. Генерация выполняется случайным выбором аллелей каждого гена.
• Далее организуется циклический процесс смены поколений:
• for k=1:G
• for j=1:N
• -Выбор родительской пары хромосом;
• -Кроссинговер;
• -Мутации;
• -Оценка функции полезности F потомков;
• -Селекция;
• end
• Замена текущего поколения новым;
• end
• Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссинговера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение.
• Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.[1]
• 1.1 Выбор родителей
• Этот оператор имитирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями функции полезности более вероятен. Например, пусть требуется минимизировать. Тогда вероятность выбора родителя с хромосомой можно рассчитать по формуле

	(1)

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

1	2	5	0,5
2	7	0	0
3	6	1	0,1
4	3	4	0,4

• 1.2 Кроссинговер (скрещивание)
• Кроссинговер, иногда называемый кроссовером, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссинговере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в таблице 2, где разрыв подразумевается между пятым и шестым локусами.[1]
• Таблица 2

Хромосома	Ген 1	Ген 2	Ген 3	Ген 4	Ген 5	Ген 6	Ген 7	Ген 8
Родителя A	f	a	c	d	g	k	v	e
Родителя B	a	b	c	d	e	f	g	h
Потомка C	f	a	c	d	g	f	g	h
Потомка D	a	b	c	d	e	k	v	e

• 1.3 Мутации
• Оператор мутации выполняется с некоторой вероятностью , т.е. с вероятностью происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска.[2]
• 1.4 Селекция
• На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности. Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.[2]
• генетический потомственность кроссинговер селекция мутация
• 2. Применение генетического алгоритма
• Генетические алгоритмы в различных формах применились ко многим научным и техническим проблемам. Генетические алгоритмы использовались при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они использовались при проектировании нейронных сетей или управлении роботами. Они также применялись при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (такие как экономика и политические системы) и когнитивные системы.
• Тем не менее, возможно наиболее популярное приложение генетических алгоритмов - оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. В других случаях, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска "хороших" значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность генетического алгоритма использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов и поиску устойчивых состояний систем нелинейных дифференциальных уравнений.
• Однако нередки случаи, когда генетический алгоритм работает не так эффективно, как ожидалось.
• Предположим есть реальная задача, сопряженная с поиском оптимального решения, как узнать, является ли генетический алгоритм хорошим методом для ее решения? До настоящего времени не существует строгого ответа, однако многие исследователи разделяют предположения, что если пространство поиска, которое предстоит исследовать, - большое, и предполагается, что оно не совершенно гладкое и унимодальное (т.е. содержит один гладкий экстремум) или не очень понятно, или если функция приспособленности с шумами, или если задача не требует строго нахождения глобального оптимума - т.е. если достаточно быстро просто найти приемлемое "хорошее" решения (что довольно часто имеет место в реальных задачах) - генетический алгоритм будет иметь хорошие шансы стать эффективной процедурой поиска, конкурируя и превосходя другие методы, которые не используют знания о пространстве поиска.
• Если же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как генетический алгоритм мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению. Если пространство гладкое и унимодальное любой градиентный алгоритм, такой как, метод скорейшего спуска будет более эффективен, чем генетический алгоритм. Если о пространстве поиска есть некоторая дополнительная информация (как, например, пространство для хорошо известной задачи о коммивояжере), методы поиска, использующие эвристики, определяемые пространством, часто превосходят любой универсальный метод, каким является генетический алгоритм. При достаточно сложном рельефе функции приспособленности методы поиска с единственным решением в каждый момент времени, такой как простой метод спуска, могли "затыкаться" в локальном решении, однако считается, что генетический алгоритм, так как они работают с целой "популяцией" решений, имеют меньше шансов сойтись к локальному оптимуму и робастно функционируют на многоэкстремальном ландшафте.
• Конечно, такие предположения не предсказывают строго, когда генетический алгоритм будет эффективной процедурой поиска, конкурирующей с другими процедурами. Эффективность генетического алгоритма сильно зависит от таких деталей, как метод кодировки решений, операторы, настройки параметров, частный критерий успеха. Теоретическая работа, отраженная в литературе, посвященной Гамам, не дает оснований говорить о выработки каких-либо строгих механизмов для четких предсказаний.
• 3. Реализация простого генетического алгоритма в MATLAB
• Согласно моему заданию я должен был написать процедуру-функцию, реализующую генетический алгоритм и с помощью составленной программы провести поиск минимума функции
• результат выполнения функции для 5 генов. Символом “*” обозначен финальный результат. Блок-схема программы
• Список литературы
• 1. http://bigor.bmstu.ru/ - База и Генератор Образовательных Ресурсов - Все учебные курсы -Эволюционные методы для решения задач проектирования и логистики.
• 2. http://ru.wikipedia.org/ - Википедия - свободная энциклопедия - поиск “Генетический алгоритм”.
• 3.http://algolist.manual.ru/ai/ga/ga1.php#ga - сайт по алгоритмам и методам
• Размещено на Allbest.ru