Применение адаптированного генетического алгоритма для решения задач размещения

Материалы Международной конференции

“Интемектуальные САПР”

the generic term world-class manufacturing(WCM). However, the range and sophistication of these techniques places WCM status beyond the aspirations and competence of many companies. Companies progress by stages toward the desired goal of global competitiveness manufactures will have to achieve world-class manufacturing status to compete effectively in global markets.

Schonberger (1987) coined the term WCM to cover the many techniques and technologies designed to enable a company to match its best competitors. Within the various professional manufacturing attention is being paid to reliability, dependent on the stage of professionalisation, there are all kind of facilities for increasing the system design of world-class manufacturing. WCM is now becoming more an area for explicit attention for all kind of manufacturing. The new concept of designing global products for global markets has emerged in the 21 century. The design of global products for global markets entails a major shift in both marketing and design philosophies for most manufacturing companies. Manufacturers worldwide are having to adapt to new conditions of world market and to new definitions of world-class performance.

Global WCM is a management philosophy that emphasises the need to meet external and internal customers needs and expectations and the importance of doing things right for world market. Reliability, quality and cost are linked, higher quality being associated with higher reliability. The reliability of items, products and facilities is an important consideration of design by world-class manufacturing techniques. WCM techniques have an important role to play in world market. Global WCM techniques are a competitive strategy involving continuous improvement of products, processes and services to improve quality, reduce costs, increase productivity and increase total customer satisfaction.

The paper is based on an ongoing research programme designed to identify how the concept of world-class manufacturing techniques can be made more relevant to achieve world market. The question in this paper is which problems the management of manufacturing may encounter when it wants to organise the global WCM management of the professional manufacturing more systematically for world market. These problems such as, determining world-class manufacturing norms, developing a world-class management methodology for world market, the demonstrability of world-class manufacturing in the professional manufacturing. The paper uses a case study to illustrate its findings based on company experiencing both rapid growth and increasing international competition.

УДК 007.001.33

А.М. Наместников

ПРИМЕНЕНИЕ АДАПТИРОВАННОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

Генетический алгоритм является эффективной процедурой оптимизации при решении широкого класса оптимизационных задач. Тем не менее, в случае много-экстремальности функции оптимизации, часто не удается найти эффективные ре, -

.

электрорадиоэлементов (ЭРЭ) на непрерывном монтажном пространстве.

Исходными данными для решения задачи размещения разногабаритных ЭРЭ являются: габариты монтажного пространства; множество элементов размещения,

характеризующиеся своими габаритными размерами (все размещаемые ЭРЭ аппроксимируются прямоугольниками); матрица связности элементов размещения.

Необходимо найти такой вариант размещения элементов на монтажном про, , суммарная длина соединений между ними - минимальная. Задача размещения ставится как задача оптимизации целевой функции, содержащую нормированную оценку суммы штрафа за перекрытие площадей размещаемых ЭРЭ и общей длины .

В основе первой фазы работы адаптированного генетического алгоритма лежит концентрация наиболее связанных друг с другом элементов. В качестве оператора мутации используется оператор переноса элемента в случайную позицию. На второй фазе алгоритма происходит замена оператора мутации на случайный сдвиг элемента в случайную сторону с одновременным изменением целевой функции с локальной на основную. Управление численными значениями генетических опера-( ) -, .

Эффективность применения адаптированного генетического алгоритма оценивалась путем проведения экспериментов со стандартным генетическим алгоритмом и системой автоматизированного проектирования ACCEL EDA, которые решали тестовую задачу размещения 56 ЭРЭ. Коэффициент заполнения монтажного пространства изменялся от 0.5 до 0.8. Среднее уменьшение суммарной длины соединений между размещаемыми ЭРЭ для адаптированного генетического алгорит-20%.

УДК 681.623

В.А. Литвиненко, Л.И. Зеленский, Р.А. Белогородцев

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МОДИФИЦИРОВАННОГО АЛГОРИТМА ОПРЕДЕЛЕНИЯ КЛИК ГРАФА

Алгоритмы определения клик графа можно разделить на следующие классы: точные алгоритмы [1-7], определяющие все клики графа; алгоритмы, выделяющие семейства клик графа [8]; приближенные алгоритмы, позволяющие определять некоторое подмножество клик графа [8]; адаптивные алгоритмы, имеющие возможность настраиваться на получение как точного, так и приближенного решения [9].

Алгоритм определения клик графа, предложенный в работе [1], определяет все клики графа и является наиболее эффективным из известных алгоритмов. В работе [9] предложено модифицировать алгоритм [1], таким образом, чтобы помимо выделения всех клик графа, т.е. получение точного решения, можно было получить и приближенное решение с точностью, которая зависит от значения управ.

с параметрической адаптацией [9].

Управляющий параметр выбирается в зависимости от соотношения количества вершин и ребер исследуемого графа. Параметр является целым числом. При

, ,

графа, т.е. получить точное решение. Если значение параметра задать 2, 3, 4 и т.д.,