Genetic Algorithms For the Linear Ordering Problem

0326657 - ÚI 2010 RIV CZ eng J - Journal Article
Krömer, P. - Snášel, V. - Platoš, J. - Húsek, Dušan
Genetic Algorithms For the Linear Ordering Problem.
[Genetické algoritmy pro problém lineárního uspořádání.]
Neural Network World. Roč. 19, č. 1 (2009), s. 65-80. ISSN 1210-0552
Institutional research plan: CEZ:AV0Z10300504
Keywords : evolutionary algorithms * genetic algorithms * linear ordering problem * combinatorial optimization
Subject RIV: IN - Informatics, Computer Science
Impact factor: 0.475, year: 2009

Linear ordering problem is a well-known optimization problem attractive for its complexity (it is an NP-hard problem), rich library of test data and variety of real world applications. In this paper, we investigate the use and performance of two variants of genetic algorithms, mutation only genetic algorithms and higher level chromosome genetic algorithm, on the linear ordering problem. Both methods are tested and evaluated on a library of real world and artificial linear ordering problem instances.

Problém lineárního uspořádání je známý optimalizační problém atraktivní z hlediska jeho výpočetní složitosti (jedná se o NP-úplný problém), existující bohaté sadě testů a množství reálných aplikací. V této práci se zabýváme výzkumem výkonnosti dvou variant genetických algoritmů, genetickým algoritmem jen s mutací a genetickým algoritmem s chromosomy vyšší úrovně, při aplikaci na problém lineárního uspořádání. Obě metody jsou testovány a vyhodnoceny na jednotlivých případech z uměle generované sady a též z knihovny reálných aplikací problému lineárního uspořádání.
Permanent Link: http://hdl.handle.net/11104/0005283