Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Информационные технологии на основе генетических алгоритмов для задачи компоновки схем электронных средств И.В. Суздальцев Научный руководитель: С.Ф. Чермошенцев, к.т.н., профессор Казанский государственный технический университет им. А.Н. Туполева Предлагается концепция решения задачи компоновки схем элек­ тронных средств по модулям с учетом критерия электромагнитной совмес­ тимости, основанная на применении генетического алгоритма. В общем случае задача компоновки решается смешанными алгорит­ мами в два этапа: начальная компоновка последовательными алгоритмами и улучшение результатов начальной компоновки итерационными процеду­ рами. Это приводит к некоторым трудностям - сложность вычислений и большие затраты машинного времени. Привлекательность генетических алгоритмов состоит в том, что они позволяют избежать этих трудностей и обеспечивают максимальное приближение к требуемому решению постав­ ленной задачи. Задача компоновки сводится к задаче разрезания гиперграфа.. Здесь вершины графа соответствуют функциональным узлам схемы. Функцио­ нальное разбиение гиперграфа H(X,V) представляется в виде хромосомы, состоящей из п генов, порядковые номера которых соответствуют номерам вершин графа. Для того чтобы начать процедуру поиска решения, создает­ ся начальная популяция р' из п генов и задается количество популяций N, в пределах которого будет выявляться оптимальное решение. Данная популяция создается случайным образом, так как заранее не известно, где именно в р' находится глобальное оптимальное решение. Ис­ пользуя начальную популяцию, можно перейти к вычислению последую­ щих популяций. Для этой цели используются три генетических оператора - кроссинговера. мутации и отбора. В качестве оператора скрещивания выступает одноточечный крос- синговер. После кроссинговера к хромосомам- кандидатам применяется генная мутация. Выбранные случайные гены меняются местами. После­ дующий оператор отбора (элитный отбор) позволяет поддерживать чис­ ленность популяции на постоянном уровне, то есть он отсеивает худших представителей популяции и оставляет хромосомы с наилучшей функцией пригодности. Функция пригодности выбирается на основании критериев, поставленных к задаче. В каждой популяции отбирается 20 хромосом. В результате образуется текущая популяция, равная р' = р' '. Процес­ сы кроссинговера, мутации и отбора повторяются до тех пор, пока номер текущей популяции не достигнет заданному количеству популяций или пока для нескольких популяций будет сохраняться неизменность функции пригодности. П О