A genetic algorithm for the optimal sequential partitioning problem
-
- Araki Hajime
- Hokkaido University
-
- Kaji Taichi
- Otaru University of Commerce
-
- Yamamoto Masahito
- Hokkaido University
-
- Suzuki Keiji
- Hokkaido University
-
- Ohuchi Azuma
- Hokkaido University
Bibliographic Information
- Other Title
-
- 遺伝的アルゴリズムによる最適系列分割問題の解法
- イデンテキ アルゴリズム ニ ヨル サイテキ ケイレツ ブンカツ モンダイ ノ カイホウ
Search this article
Abstract
The optimal sequential partitioning problem is defined as the problem to find the minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the prece-dence relationships among the elements are satisfied. The heuristic algorithm based on a tabu search for this problem has been proposed(2). However, there is a tendency for the solutions obtained using the tabu search approach to be trapped in bad local optima in the parallel graphs with random costs of edges<br> In this paper we present the genetic algorithm for the optimal sequential partitioning problem. We developeffective two point partial order crossover satisfying sequential conditions, which preserve better block that has the larger sum of edge costs of block. In this crossover we introduce roulette selection method to escape local optima. We also assess the effectiveness of the developed algorithm. The results show that this proposed algorithm outperforms, in terms of solution quality, any other algorithm using tabu search.
Journal
-
- IEEJ Transactions on Electronics, Information and Systems
-
IEEJ Transactions on Electronics, Information and Systems 120 (2), 215-221, 2000
The Institute of Electrical Engineers of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679586734976
-
- NII Article ID
- 130006845274
- 10006759355
-
- NII Book ID
- AN10065950
-
- ISSN
- 13488155
- 03854221
-
- HANDLE
- 2115/64535
-
- NDL BIB ID
- 4973442
-
- Data Source
-
- JaLC
- IRDB
- NDL
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed