Vhnízděné genetické algoritmy pro distribuované optimalizační problémy

The Nested Genetic Agorithms for Distributed Optimization Problems

conference paper

en

Firstly, we review basic principles of the distributed modeling approach in optimization and present introduction to the formal framework based on the concept of a distributed optimization program. The framework is a general one and may be utilized for various classes of decision problems. The DOPs (distributed optimization programs) are introduced as syntactical entities containing certain optimization elements and based on composition rules. They may describe both basic and advanced mathematical programs (e.g., dynamic, stochastic, multistage, and hierarchical) and also game theory models. In addition, more complicated models can be derived from these building stones and further transformed in the syntactical correct way. Although the introduced descriptions are particularly designed for manipulations of programs structures, semantics for certain DOPs can also be defined. Hence, the next challenge is to search promising solutions in the feasible sets of optimization elements of DOPs. Therefore, several genetic algorithms (GAs) are chosen to search in separate feasible sets and they may also exchange information about different populations for achieved solutions of DOP elements in various ways. The general inspiration comes from decomposition techniques in scenario-based multistage programs, so the name nested GAs is used in our case. The computational results and implementation description are presented for the specific min-max problems that are chosen as elementary prototype instances.

V první části jsou shrnuty základní principy distribuované modelování v oblasti optimalizace a je předložen úvod do formálního rámce založeného na konceptu distribuovaného optimalizačního programu. Tento rámec je obecný a může být využit pro různé druhy rozhodovacích problémů. Koncept DOP (distribuované optimalizační programy) je představen jako souhrn syntaktických entit obsahující vybrané optimalizační prvky a pravidla jejich kompozice. Mohou popisovat základní i pokročilé matematické programování (např. dynamické, stochastické, vícestupňové a hierarchického), a také modely teorie her. Z těchto stavebních prvků lze vytvářet složitější modely následně je upravovat dle syntaktických pravidel. Ačkoliv je tento popis navržen hlavně pro manipulaci s programovými strukturami, může být definována i sémantika pro vybrané DOP. Další výzvou je hledat řešení v množinách přípustných řešení jednotlivých optimalizačních prvků DOP. K tomuto účelu byly použity genetické algoritmy, které si zde mohou různými způsoby vyměňovat informace o řešeních hledaných v různých populacích různých prvků. Základní inspirace pochází z dekompozičních technik používaných pro manipulace se scénáři ve vícestupňovém programování; v našem případě používáme pojem "vhnízděné genetické algoritmy". Jsou uvedeny výsledky výpočtů a popis implementace pro specifické min-max problémy, které byly vybrány pro ověření v článku uvedených myšlenek.

Firstly, we review basic principles of the distributed modeling approach in optimization and present introduction to the formal framework based on the concept of a distributed optimization program. The framework is a general one and may be utilized for various classes of decision problems. The DOPs (distributed optimization programs) are introduced as syntactical entities containing certain optimization elements and based on composition rules. They may describe both basic and advanced mathematical programs (e.g., dynamic, stochastic, multistage, and hierarchical) and also game theory models. In addition, more complicated models can be derived from these building stones and further transformed in the syntactical correct way. Although the introduced descriptions are particularly designed for manipulations of programs structures, semantics for certain DOPs can also be defined. Hence, the next challenge is to search promising solutions in the feasible sets of optimization elements of DOPs. Therefore, several genetic algorithms (GAs) are chosen to search in separate feasible sets and they may also exchange information about different populations for achieved solutions of DOP elements in various ways. The general inspiration comes from decomposition techniques in scenario-based multistage programs, so the name nested GAs is used in our case. The computational results and implementation description are presented for the specific min-max problems that are chosen as elementary prototype instances.

Genetické algoritmy, minmax problém, distribuované optimaoizační programy, vhnízdění

Genetic algorithms, minmax problems, distributed optimization programs, nested decomposition

2011

19.10.2011

978-988-18210-9-6

Proceedings of The World Congress on Engineering and Computer Science 2011

480–484

5