• Новости
  • Темы
    • Экономика
    • Здоровье
    • Авто
    • Наука и техника
    • Недвижимость
    • Туризм
    • Спорт
    • Кино
    • Музыка
    • Стиль
  • Спецпроекты
  • Телевидение
  • Знания
    • Энциклопедия
    • Библия
    • Коран
    • История
    • Книги
    • Наука
    • Детям
    • КМ школа
    • Школьный клуб
    • Рефераты
    • Праздники
    • Гороскопы
    • Рецепты
  • Сервисы
    • Погода
    • Курсы валют
    • ТВ-программа
    • Перевод единиц
    • Таблица Менделеева
    • Разница во времени
Ограничение по возрасту 12
KM.RU
Рефераты
Главная → Рефераты → Информатика, программирование
  • Новости
  • В России
  • В мире
  • Экономика
  • Наука и техника
  • Недвижимость
  • Авто
  • Туризм
  • Здоровье
  • Спорт
  • Музыка
  • Кино
  • Стиль
  • Телевидение
  • Спецпроекты
  • Книги
  • Telegram-канал

Поиск по рефератам и авторским статьям

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

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

В.В Курейчик

В последнее время появились новые «нестандартные» архитектуры генетического поиска, позволяющие в большинстве случаев решать проблему предварительной сходимости алгоритмов. Это методы миграции и искусственной селекции [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.

Дата добавления: 29.03.2005

База рефератов на портале KM.RU существует с 1999 года. Она пополнялась не только готовыми рефератами, докладами, курсовыми, но и авторскими публикациями, чтобы учащиеся могли использовать их и цитировать при самостоятельном написании работ.


Это популяризирует авторские исследования и научные изыскания, что и является целью работы истинного ученого или публициста. Таким образом, наша база - электронная библиотека, созданная в помощь студентам и школьникам.


Уважаемые авторы! Если Вы все же возражаете против размещения Вашей публикации или хотите внести коррективы, напишите нам на почту info@corp.km.ru, мы незамедлительно выполним Вашу просьбу или требование.


официальный сайт © ООО «КМ онлайн», 1999-2025 О проекте ·Все проекты ·Выходные данные ·Контакты ·Реклама
]]>
]]>
Сетевое издание KM.RU. Свидетельство о регистрации Эл № ФС 77 – 41842.
Мнения авторов опубликованных материалов могут не совпадать с позицией редакции.

Мультипортал KM.RU: актуальные новости, авторские материалы, блоги и комментарии, фото- и видеорепортажи, почта, энциклопедии, погода, доллар, евро, рефераты, телепрограмма, развлечения.

Карта сайта


Подписывайтесь на наш Telegram-канал и будьте в курсе последних событий.


Организации, запрещенные на территории Российской Федерации
Telegram Logo

Используя наш cайт, Вы даете согласие на обработку файлов cookie. Если Вы не хотите, чтобы Ваши данные обрабатывались, необходимо установить специальные настройки в браузере или покинуть сайт.