Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 11
Текст из файла (страница 11)
По аналогии с ДНК, в программной системе,использующей ГА, хромосома может представлять собой битовуюпоследовательность. Для достаточно широкого класса задач, такоепредставление дает хорошие результаты. Например, в задаче нахожденияэкстремума функции на отрезке, битовая хромосома можетинтерпретироваться как двоичная запись аргумента функции. Для болеесложных задач роль гена могут играть элементы, устроенные болеесложно, чем один бит. Заметим только, что в результате операцийрепродукции, могут получаться произвольные комбинации генов, которыедолжны иметь осмысленную интерпретацию.Репродукция популяции происходит в условиях естественного отбора,предполагающего выживание и размножение «лучших», наиболееприспособленных к конкретным условиям, хромосом.
Для реализацииконцепции отбора необходимо ввести способ сопоставления (сравнения)различных хромосом в соответствии с их возможностями решенияпоставленной задачи. В программной системе роль окружающей средыиграет оценочная функция. Оценочная функция для каждой хромосомывозвращает число, определяющее степень ее пригодности. Собственноговоря, именно в оценочной функции содержится алгоритм расшифровкихромосомы. Например, при поиске максимума на отрезке роль оценочнойфункции может играть сама функция, заданная в условии задачи.
Стоитотметить, что при использовании важно не просто абсолютное значениеоценочной функции, а возможность применения ее как меры длясопоставления хромосом. Для осуществления более точного и гибкогоотбора оценочная функция должна иметь достаточно широкую областьзначений (0 и 1, да и нет, будет явно недостаточно).В процессе регенерации популяции участвуют только хромосомы,обладающие достаточно высокой степенью пригодности. Выбор«хороших» хромосом-родителей может происходить по разнымалгоритмам. Простейший (но дающий хорошие результаты) алгоритмзаключается в упорядочение всех хромосом по убыванию их пригодностии отбрасывании худшей половины. После этого, из оставшейся частихромосомы для дальнейшей регенерации популяции могут выбиратьсяслучайным образом. Другой алгоритм выбора хромосом-родителей носитназвание «рулетки».
Хромосомы также упорядочиваются по убыванию ихпригодности, затем пригодности всех хромосом суммируются. Для выборакаждой хромосомы-родителя берется случайное число из интервала отнуля до этой Суммы. Перебирая упорядоченную последовательностьхромосом, снова суммируется их пригодность. При этом выбирается тахромосома из последовательности, на пригодности которой суммадостигает заданное число. Очевидно, что при таком алгоритме,вероятность быть выбранными значительно выше у хромосом,расположенных в начале последовательности и, следовательно, имеющих60большую степень пригодности.
Заметим, что и в первом, и во второмслучаях одна хромосома может несколько раз принимать участие врегенерации популяции.На первом шаге ГА, начальная популяция порождается случайнымобразом. Каждая следующая популяция получается в результатерепродукции с участием «лучших» хромосом. При этом та или инаямодель отбора, определяет, каким образом следует строить популяциюследующего поколения. Возможна полная замена популяции, «старые»хромосомы из предыдущего поколения «умирают», давая место новым.
Неменее популярна так называемая стратегия «элитизма», при которойнесколько лучших хромосом переходят в следующее поколение безизменений. В любом случае каждое следующее поколение будет в среднемлучше предыдущего. Будем считать, что размер популяции при сменепоколений остается постоянным.Смена поколений в популяции является итеративным процессом.
Вкачестве решения задачи оптимизации будет выбрана наилучшаяхромосома из последней популяции. При этом решение об остановке ГАможет быть принято в соответствии с различными стратегиями. Например,при инициализации генетического эксперимента можно задатьмаксимальное число итераций. В этом случае независимо от получаемогона каждом шаге результата ГА проработает фиксированное число раз.Если же ГА работает в интерактивном режиме, то пользователь послекаждой итерации может получать наилучшую хромосому, оцениватьсоответствующее ей решение задачи и принимать решение об остановкеили продолжении генетического эксперимента.
Более гибкий алгоритмстроится по аналогии с численными методами и основывается на заданииточности, с которой необходимо найти решение. Процесс останавливается,когда пригодность хромосом перестает заметно улучшаться (т.е.пригодность наилучшей хромосомы из последней популяции отличаетсяот пригодности наилучшей хромосомы из предыдущей не более чем навеличину заданной точности). Также по аналогии с терминологией,принятой в численных методах, можно говорить о сходимости ГА.Скорость сходимости ГА для каждой конкретной задачи определяетсямногими факторами.
Во-первых, на работу алгоритма влияют егопараметры:• интенсивная мутация снижает скорость алгоритма и может серьезноповлиять на сходимость;• слишком малая вероятность мутации затрудняет выход алгоритма излокальных экстремумов;• большие популяции сходятся дольше;• при малом размере популяции возрастает вероятность остановки влокальном экстремуме.61Также скорость сходимости ГА зависит от модели отбора, алгоритмавыбора хромомосом-родителей.В простейшей модели ГА будем рассматривать только две стратегиирепродукции популяции - скрещивание двух хромосом и мутациюСкрещивание определяет поступательное развитие популяции и состоит внаследование генетического материала достаточно «хороших» родителей.В результате скрещивания доля «хороших» хромосом в общей массе будетвозрастать.Поступательное развитие в условиях некоторой среды в общем случае неявляется монотонным и непрерывным.
На пути к глобальному экстремумувозможно бесконечное множество локальных. Выбирая лучших внебольшой окрестности локального экстремума, существует опасностьвырождения (зацикливания) ГА. И глобальный экстремум, являющийсяконечной целью оптимизации, никогда не будет достигнут Мутацияпривносит необходимый элемент случайности, позволяющий преодолетьлокальный экстремум. При этом мутации должно подвергаться достаточнонебольшое количество хромосом, чтобы разброс значений пригодностихромосом не был слишком велик, и ГА достаточно быстро сходился.Очевидно, что мутации могут быть как полезными, так и ухудшающимихромосомы.
В первом случае механизм наследования (скрещивание)закрепит это свойство в следующих поколениях. В противном же случае,механизм естественного отбора сократит влияние регрессирующиххромосом на остальную популяцию, и со временем нежелательноесвойство будет удалено из популяции.Рис. 11. Генетический алгоритмВозможностью мутации выгодно отличает ГА от градиентных алгоритмов,которые в чистом виде пригодны только для унимодальных задач (целеваяфункция имеет единственный локальный, он же и глобальный, экстремум).В то же время к достоинствам метода градиентного спуска относитсявысокая скорость нахождения экстремума.
В свою очередь, полныйперебор хотя и гарантирует нахождение действительно оптимальногорешения, но требует слишком больших вычислительных затрат. ГА можно62рассматривать как комбинацию техники полного перебора (мутация,скрещивание) и градиентных методов (естественный отбор).Итак, последовательность шагов генетического алгоритма следующая(Рис. 11). Случайным образом инициализируется популяция, и всехромосомы сравниваются в соответствии с выбранной функцией оценки.Далее (возможно многократно) выполняется процедура репродукциипопуляции.
Хромосомы-родители выбираются случайным образомпропорционально степени их пригодности. Репродукция происходит либоиндивидуально для одного родителя путем мутации хромосомы, либо длядвух родителей путем скрещивания. Получившиеся хромосомыоцениваются в соответствии с заданной оценочной функцией ипомещаются в популяцию. В качестве решения выбирается хромосома снаибольшей степенью пригодности из последней полученной популяции.ГрафыОдним из наиболее распространенных способов представления данных,позволяющих описывать сложные зависимости между элементами,является граф (и его частные случаи, имеющие самостоятельное значение,- деревья, бинарные деревья, списки и т.д.).
Представление информации ввиде графов и алгоритмы работы с ними широко применяются припостроении компиляторов, различных автоматов, решении комбинаторныхзадач и т.д.Алгоритмы работы с графами давно известны и хорошо проработаны. Нокаждая программная система, использующая методы анализа графов,сталкивается с выбором внутреннего представления для их хранения иобработки. Эффективность работы с графами, которые для реальных задачмогут содержать большое число узлов и ребер, во многом определяетсяудачностью выбора внутреннего представления.
Граф представляет собойсовокупность множества вершин и ребер G(V, E). Как правило,информационные структуры, соответствующие вершинам (V) и ребрамграфа (E), имеют последовательное представление. Для отображенияЕ —> V * V (каждому ребру ставится в соответствие пара вершин - начало иконец) используются различные способы: матрицы смежности, матрицыинцидентности, списочные структуры. Каждый способ имеетопределенные достоинства и недостатки, и выбор определяетсяспецификой конкретной задачи.В реальных задачах исходная информация для инициализации конкретногографа отличается большим объемом и хорошей структурированностью.Она может быть получена как непосредственно от пользователя, так и издругого приложения.
В качестве внешнего представления удобно63использовать текстовый файл, содержащий описание всех вершин и реберграфа. Такое внешнее представление также можно использовать дляобмена данными между разными приложениями. Как следствие, приработе с графами присутствует предварительный этап преобразованияинформации о конкретном графе во внутреннее представление системы.Преобразование графа из внешнего формата во внутреннее представлениеи обратно, а так же функции доступа к отдельным элементам графа и ихсвойствам могут быть оформлены в виде библиотеки.Пример решения задачиРассмотрим последовательность шагов создания программы сиспользованием приемов быстрого прототипирования на примере решениязадачи о нахождении пути между двумя вершинами на графе [5].Жизненный цикл любой программы включает анализ требований,проектирование и создание реализации, удовлетворяющей этимтребованиям.
Назовем эту реализацию первым прототипом программы.Для простых задач первый прототип может быть и последним. В общем жеслучае, требования анализируются еще раз, уточняются и детализируются.В соответствии с этим пересматривается проект программы и создаетсявторой прототип. Заметим, что важность этапа проектирования заметновозрастает при таком подходе. Для использования преимуществтехнологии прототипирования программа должна быть гибкой, легкорасширяемой и хорошо документированной.И первый, и второй прототип - это законченные работающие программы.Первый прототип может отличаться от второго детальностью требований,эффективностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
