Доклад: Перспективные архитектуры генетического поиска

В.В Курейчик

В последнее время появились новые «нестандартные» архитектуры генетического поиска, позволяющие в большинстве случаев решать проблему предварительной сходимости алгоритмов. Это методы миграции и искусственной селекции [1], метагенетической параметрической оптимизации [2], стохастически-итерационные генетические и поисковые [3], ?прерывистого равновесия? [4], объединения генетического поиска и моделирования отжига [5].В [1] в отличие от обыкновенных ГА выполняется макроэволюция, т.е. создается не одна популяция, а некоторое множество популяций. Генетический поиск здесь осуществляется путем объединения родителей из различных популяций. В отличие от [1-5] предлагается модифицированная архитектура генетического поиска с миграцией и искусственной селекцией (рис.1.).Здесь блоки 1 - 3 представляют собой простой или модифицированный ГА. Отметим, что в каждом блоке выполняется своя искусственная селекция. В первом блоке селекция на основе рулетки. Во втором блоке используется селекция на основе заданной шкалы. В третьем блоке - элитная селекция. В блок миграции каждый раз отправляется лучший представитель из популяции. Связь между блоками 1 - 3 осуществляется путем последовательной цепочки 1 - 2, 2 - 3.Отметим, что можно организовать различное количество связей между блоками, такого типа, как по принципу полного графа, по принципу звезды и т.д. Такая схема селекции в случае наличия большого количества вычислительных ресурсов может быть доведена до N блоков. Причем N-1 блоков могут параллельно осуществлять эволюционную адаптацию и через блоки миграции обмениваться лучшими представителями решений. Последний блок собирает лучшие решения, может окончить результат работы или продолжить генетическую оптимизацию. Такая схема оптимизации в отличие от существующих позволяет во многих случаях выходить из локальных оптимумов. Для повышения эффективности такой архитектуры в САПР используют метагенетическую оптимизацию (МГО). Она заключается в следующем (рис.2). Основным является первый блок, в котором осуществляется реализация генетического алгоритма, генерация новых решений, определение моделирующей функции и использование предыдущих решений для генерации лучших результатов. Второй блок позволяет использовать «историю» предыдущих решений для генерации лучшего множества параметров. В третьем блоке генерируется новое множество оптимизационных параметров. Используя МГО оптимизационный процесс в САПР, можно случайным, направленным или случайно-направленным способом генерировать начальные популяции, моделировать каждую индивидуальность посредством выполнения ГА на основе реализации генетических операторов. Можно случайно выбирать родителей из популяции с вероятностью селекции каждого элемента пропорционально его значению. Причем, вероятность выполнения каждого оператора может определяться пропорционально его öåëåâîé ôóíêöèè. Окончательное множество параметров селектируется после моделирования из конечной популяции. Отметим, что для каждой задачи проектирования СБИС будет строиться свой конкретный метагенетический алгоритм.

Рис 1. Модифицированная схема миграции и искусственной селекции.

Рис. 1

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

Метод прерывистого равновесия [4] основан на палеонтологической теории прерывистого равновесия, которая описывает быструю эволюцию за счет вулканических и других изменений земной коры. Для применения данного метода в технических задачах в предлагается после каждой генерации случайным образом перемешивать индивидуальности в популяции, а затем формировать новые текущие генерации. Здесь можно предложить, как аналог из живой природы, бессознательный отбор родительских пар и синтетический отбор лучших родительских пар. Далее случайным образом смешать результаты обоих отборов и не оставлять размер популяции постоянным, а управлять им в зависимости от наличия лучших индивидуальностей. Такая модификация метода прерывистого равновесия может позволить сократить неперспективные популяции и расширить популяции, в которых находятся лучшие индивидуальности. Согласно [4] метод прерывистого равновесия - это мощный стрессовый метод изменения окружающей среды, который используется для эффективного выхода из локальных ям.

Объединение ГА и моделирование отжига позволяют получать более качественные результаты за счет усложнения процедуры оптимизации [5]. Например, на основе простого ГА можно получить некоторое подмножество родителей с лучшими характеристиками и для одного из них (наилучшего) или некоторого подмножества применить оптимизационную процедуру моделирования отжига. Такое объединение можно делать различными способами. К сожалению, процедуры моделирования отжига требуют больших вычислительных затрат. Поэтому, такие подходы применяют при проектировании элементов топологии внутри ячеек, когда их число 50.

Отметим, что основные задачи повышения качества решений проектирования СБИС с применением ГА - это выход из локальных ям, а также оптимальный выбор генетических операторов и методов селекции.

Список литературы

Potts C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans. on Systems, Man and Cybernetics, vol.24, No.1, Sammary 1994. P. 73 - 86.

Shahookar K.,Mazmunder P. A Genetic Approach to standart Cell Placement Using Meta-Genetic Parameter Optimization, IEEE Trans. on CAD, Vol.9, No.5, May, 1990. P. 500 - 511.

Ackley D.H. A connectionist Machine for Genetic Hillclimbing. Kluwer Academic Publishers, Boston, MA, 1987. - 240 г.

Cohoon J.P., Paris W.D. Genetic Placement , IEEE Trans. on CAD, Vol.6, No 6, November, 1987. P. 956 - 964.

Davis L., ed. Genetic Algorithms and Sivulated Annealing. San Mateo. Morgan Kaufman Publisher, 1987. - 216 p.