Генетические алгоритмы и традиционные методы оптимизации

Примечание

В качестве исходной информации в представленной схеме обуче­ния выступают пары обучающих данных, а конечный результат представ­ляет собой отображение входного пространства данных в выходное. Из­ложенный метод обладает как способностью «обучать» соответствующее отображение по имеющимся примерам, так и свойством обобщения. Это означает, что если на вход такой нечеткой системы будут поданы новые сигналы (не присутствовавшие в обучающей выборке), то сформирован­ное отображение будет генерировать удовлетворительные выходные сиг-

3. 10. Проектирование базы нечетких правил на основе численных данных 119

Таблица 3.6.Траектория движения грузовика, стартовавшего из точки (хь.*>) = (-100,180°)
1	X	♦ П	в[°]
	-100,00	180,00	45,00
	- 98,52	155,67	34,02
	- 92,08	133,22	28,56
	- 82,05	114,04	27,93
	- 70,21	95,24	23,05
	- 57,37	79,54	13,74
	-44,23	70,01	13,18
	-31,78	60,86	14,35
	- 20,47	50,92	23,09
	-11,52	35,18	14,35
	-4,59	25,01	15,71
	0,09	14,14	14,37
	2,41	4,19	10,58
	2,66	-3,17	0,77
	1,83	-3,71	-0,91
	0,99	-3,07	-1,53
	0,35	-2,00	-1,45
	-0,03	-0,98	-1,07

налы. По этой причине рассматриваемый метод отождествляется с очень универсальной нечеткой системой без модели со способностью к обу­чению {model-free trainable fuzzy system), которая может применяться для широкого спектра задач управления. Термин без модели (model-free) означает, что для решения задачи не нужна математическая модель про­цесса управления, а определение со способностью к обучению {train-able) - что система может накапливать знания по примерам. О достоин­ствах метода свидетельствует то, что:

1) это универсальный метод создания базы нечетких правил на ос­нове численных данных; его реализация может трактоваться как первый

		Глава 3. Нечеткие множества	и нечеткий вывод
Таблица 3.7. Нечеткие правила, сгенерированные данным из табл. 3.1, и степени истинности этих правил	по обучающим
i	IF	THEN 0ЭТО	SP
хэто	фэто
	М2	МЗ	D3	0,19
	М2	D3	D3	0,23
	М2	D3	D2	0,24
	М2	D3	D2	0,11
	М1	D2	D2	0,21
	М1	D2	D2	0,37
	М1	D2	D2	0,39
	М1	D2	D2	0,46
	Ml	D1	D2	0,32
	S	D1	D2	0,54
	S	D1	D2	0,69
	S	D1	D2	0,43
	S	S	D1	0,39
	S	S	S	0,64
	S	S	S	0,62
	S	S	S	0,61
	S	S	S	0,69
	S	S	S	0,80

этап построения модуля нечеткого управления в случае, когда вместо ба­зы правил имеются только численные данные;

2) это простая процедура построения базы правил, благодаря ко­
торой не требуется длительное итеративное обучение и, следовательно,
на создание базы правил требуется значительно меньше времени по
сравнению, например, с нейро-нечеткой (neuro-fuzzy) системой;

3) существует широкая свобода подбора функций принадлежнос­
ти, что обеспечивает достаточную гибкость при проектировании систем
для различных приложений.

М,

3. 10. Проектирование базы нечетких правил на основе численных данных 121

D,	D3			M,
D.	D,		D,	M3
М3	D,	^D2
М3	M,	S	D,	^D3
		M2	M,	D3
D3	M,		M3	M,
D3			M3	M,

M₂ M, S D, D₂

х=0 х=150 рузовика, управляемого предложенной нечеткой

Рис. 3.42. Распределение обучающих данных и результирующая форма сгенериро­ванной на их основе базы правил, для задачи парковки грузовика.

Глава 3. Нечеткие множества и нечеткий вывод

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

[I] Bellman R. E, Giertz M, On the analytical formalism of fuzzy sets,
Information Siences, 1975, vol. 5, s. 149-156.

[2] BezdekJ. C, Pal S. K., (red.), Fuzzy Models for Pattern Recognition, IEEE, New York 1992

[3] Brown M., Harris C, Neurofuzzy Adaptive Modelling and Control, Prentice Hall, New York 1994.

[4] Cox E., The Fuzzy Systems Handbook, Academic Press, London 1994

[5] Czogala E., Pedrycz W., Elementy i metody teoni zbiorow rozmytych, PWN, Warszawa 1985.

[6] De Silva С W., Inteligent Control: Fuzzy Logic Applications, CRC Press, Boca Raton, 1995

[7] Driankov D., Hellendoorn K, Reinfrank M, An Introduction to Fuzzy Con­trol, Springer-Verlag, Berlin 1993.

[8] Dubois D., Prade H., Operations on fuzzy numbers, International Journal System Science, 1978, vol. 9, s. 613-626.

[9] Dubois D., Prade H., Fuzzy Sets and Systems: Theory and Applications, Academic Press, San Diego 1980.

[10] Fukami S., Mizumoto M, Tanaka K, Some considerations of fuzzy condi­tional inference, Fuzzy Sets and Systems, 1980, vol. 4, s. 243-273.

[II] Harris С 1, Moore С G, Brown M, Intelligent Control: Aspects of fuzzy
logic and neural nets, World Scientific, Singapore 1993.

[12] Hirota K, Ed., Industrial Applications of Fuzzy Technology, Springer,

1993. [13] lager R., Fuzzy Logic in Control, Thesis Technische Universiteit Delft,

Delft 1995. [ 14] Jamshidi M, Vadiee N., Ross T. J., (red.), Fuzzy Logic and Control, Prentice

Hall, Englewood 1993.

[15] KacprzykJ., Zbiory rozmyte w analizie systemowej, PWN, Warszawa 1986 [16] Klir G. J., Folger T. A., Fuzzy Sets, Uncertainty and Information. Prentice

Hall, Englewood Cliffs 1988. [17] Kluska J., Sterowanie z logikq rozmytq, Rzeszow: Zeszyty Naukowe

Politechniki Rzeszowskiej, 1992, nr 104, Elektrotechnika, z. 12. [18] Kong S. G., Kosko В., Comparison of Fuzzy and Neural Truck Backer

Upper Control Systems, Proc. IJCNN-90, June 1990, vol. 3, s. 349-358. [19] Kosko В., Neural Networks and Fuzzy Systems, Prentice Hall, Englewood

Cliffs 1992. [20] Kruse R., Gebhardt J., Klawonn R, Foundations of Fuzzy Systems, John

Wiley, Chichester 1994.

[21] Lee С. С, Fuzzy Logic in Control Systems: Fuzzy Logic Controller — Pan

1, IEEE Transactions on Systems, Man and Cybernetics, 1990, vol. 20. nr 2.
_s. 404-418.

[22] Lee С. С, Fuzzy Logic in Control Systems: Fuzzy Logic Controller — part II, IEEE Transactions on Systems, Man and Cybernetics, 1990, vol. 20, nr

2, s. 419-435.

[23] Mizumoto M., Fukami S., Tanaka K, Some Methods of Fuzzy Reasoning, w: Advances in Fuzzy Set Theory and Applications, Gupta M. M., Ragade R. K., Yager R. R. (red.), North-Holland 1979

[24] Nguyen D., Widrow В., The Truck Backer-Upper: An Example of Self-Learning in Neural Network, IEEE Contr. Syst. Mag., 1990, vol. 10, nr

3, s. 18-23.

[25] Me J., Linkens D., Fuzzy-Neural Control, Prentice Hall, New York 1995. [26] Pedrycz W, Fuzzy Control and Fuzzy Systems, New York, John Wiley

1993. [27] Slupecki J., Halkowska K., Pirog-Rzepecka K, Logika i teoria mnogosci,

PWN, Warszawa 1994. [28] Takagi Т., Sugeno M, Fuzzy Identification of Systems and Its Applications

to Modeling and Control, IEEE Transactions on Systems, Man and

Cybernetics, 1985, vol. 15, s. 116-132. [29] Terano T, Asai K, Sugeno M., Fuzzy Systems Theory and its Applications,

Academic Press, London 1992. [30] Wang L. X. Mendel J. M, Generating Fuzzy Rules by Learning from

Examples, IEEE Transactions on Systems, Man, and Cybernetics,

November/December 1992, vol. 22, nr 6, s. 1414-1427. [31] Wang L. X, Adaptive Fuzzy Systems and Control — Design and Stability

Analysis, Prentice Hall, Englewood Clifffs 1994. [32] Yager R. R., Filev D. P., Podstawy modelowania i sterowania rozmytego,

WNT, Warszawa 1995.

[33] YanJ., Ryan M, Power J., Using Fuzzy Logic, Prentice Hall, London 1994. [34] Zadeh L. A.. Fuzzy Sets, Information and Control, 1965, vol. 8, s. 338-353. [35] Zimmermann H. J., Fuzzy Set Theory, Kluwer Academic Publishers,

Boston//Dordrecht/London 1994.

ГЛАВА4

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

4.1. Введение

Нейронные сети были созданы в результате наблюдения за естест­венными процессами, происходящими в нервной системе живых су­ществ, и попыток воспроизведения этих процессов. Термин нейрон, обозначающий основной исполнительный элемент искусственных нейронных сетей, был непосредственно заимствован из теории при­родных нервных систем.

Аналогично, генетические алгоритмы возникли в результате на­блюдения и попыток копирования естественных процессов, происхо­дящих в мире живых организмов, в частности, эволюции и связанной с ней селекции (естественного отбора) популяций живых существ. Ко­нечно, при подобном сопоставлении нейронных сетей и генетических алгоритмов следует обращать внимание на принципиально различ­ную длительность протекания упоминаемых естественных процес­сов, т.е. на чрезвычайно быструю обработку информации в нервной системе и очень медленный процесс естественной эволюции. Однако при компьютерном моделировании эти различия оказываются несу­щественными.

Идею генетических алгоритмов высказал Дж. Холланд [21] в конце шестидесятых - начале семидесятых годов XX века. Он заин­тересовался свойствами процессов естественной эволюции (в том числе фактом, что эволюционируют хромосомы, а не сами живые су­щества). Холланд был уверен в возможности составить и реализо­вать в виде компьютерной программы алгоритм, который будет ре­шать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими по­следовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные про­цессы в поколениях таких хромосом. В них были реализованы меха­низмы селекции и репродукции, аналогичные применяемым при есте­ственной эволюции. Так же, как и в природе, генетические алгоритмы осуществляли поиск «хороших» хромосом без использования ка­кой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособ­ленность. Механизм селекции заключается в выборе хромосом с на­ивысшей оценкой (т.е. наиболее приспособленных), которые репроду­цируют чаще, чем особи с более низкой оценкой (хуже приспособлен­ные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация - это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее

4.2. Генетические алгоритмы и традиционные методы оптимизации 125

создать две совершенно новые хромосомы потомков путем комбини­рования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах.

В генетических алгоритмах применяется ряд терминов, заимст­вованных из генетики, прежде всего гены и хромосомы, а также попу­ляция, особь, аллель, генотип, фенотип.

Генетические алгоритмы применяются при разработке про­граммного обеспечения, в системах искусственного интеллекта, опти­мизации, искусственных нейронных сетях и в других отраслях знаний. Следует отметить, что с их помощью решаются задачи, для которых ранее использовались только нейронные сети. В этом случае генети­ческие алгоритмы выступают просто в роли независимого от нейрон­ных сетей альтернативного метода, предназначенного для решения той же самой задачи. Примером может служить задача коммивояже­ра [33], изначально решавшаяся при помощи сети Хопфилда [28]. Ге­нетические алгоритмы часто используются совместно с нейронными сетями. Они могут поддерживать нейронные сети или наоборот, либо оба метода взаимодействуют в рамках гибридной системы, предназ­наченной для решения конкретной задачи. Генетические алгоритмы также применяются совместно с нечеткими системами.

Генетический алгоритм представляет собой метод, отражаю­щий естественную эволюцию методов решения проблем, и в первую очередь задач оптимизации. Генетические алгоритмы - это процеду­ры поиска, основанные на механизмах естественного отбора и насле­дования. В них используется эволюционный принцип выживания наи­более приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частно­сти, генетические алгоритмы:

1) обрабатывают не значения параметров самой задачи, а их
закодированную форму;

2) осуществляют поиск решения исходя не из единственной
точки, а из их некоторой популяции;

3) используют только целевую функцию, а не ее производные
либо иную дополнительную информацию,

4) применяют вероятностные, а не детерминированные пра­
вила выбора.

Перечисленные четыре свойства, которые можно сформулиро­вать также как кодирование параметров, операции на популяциях, ис­пользование минимума информации о задаче и рандомизация опера­ций приводят в результате к устойчивости генетических алгоритмов и к их превосходству над другими широко применяемыми технологи­ями [15].

а 4. Генетические алгоритмы

4.3. Основные понятия генетических алгоритмов

4.3. Основные понятия генетических алгоритмов

При описании генетических алгоритмов используются опреде­ления, заимствованные из генетики. Например, речь идет о популя­ции особей,а в качестве базовых понятий применяются ген, хромосо­ма, генотип, фенотип, аллель. Также используются соответствую­щие этим терминам определения из технического лексикона, в част­ности, цепь, двоичная последовательность, структура.

Популяция - это конечное множество особей.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точка­ми в пространстве поиска (search points). В некоторых работах осо­би называются организмами.

Хромосомы (другие названия - цепочки или кодовые последо­вательности) - это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

Генотип или структура - это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо еди­ничные хромосомы (в довольно распространенном случае, когда ге­нотип состоит из одной хромосомы).

Фенотип - это набор значений, соответствующих данному ге­нотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи.

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функ­цией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволя­ет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наиболь­шие значения функции приспособленности) в соответствии с эволюци­онным принципом выживания «сильнейших» (лучше всего приспосо­бившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функ­ционирование генетических алгоритмов и должна иметь точное и кор­ректное определение. В задачах оптимизации функция приспособлен­ности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функ­ция преобразуется, и проблема сводится к максимизации. В теории уп­равления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой ите­рации генетического алгоритма приспособленность каждой особи дан­ной популяции оценивается при помощи функции приспособленности,

и на этой основе создается следующая популяция особей, составляю­щих множество потенциальных решений проблемы, например, задачи оптимизации.

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

Дата добавления: 2015-06-04