Presentation | 1997/5/22 Problem Solving based on the Control of Complexity : for Solving the Large Scale Traveling Salesman Problem Seizaburo Niitsuma, Tsutomu Nakashima, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | This paper describes a meta-heuristics called an Inductive Algorithm, which is a problem-solving paradigm based on abstraction and analogical reasoning. The algorithm have been applied to combinatorial optimization prob-lems, for example, knapsack problems and traveling salesman problems (TSP) including hundreds of cities. The algorithm is developed which makes it possible to solve large scale TSPs consisting of scores of thousands of cities. To prevent a combinatorial explosion from happening, a vew point of control of problem complexity is introduced. The control is done by abstraction and setting scopes. The modified algolithm is applicable to TSP including 85,900 cities. Inductive Algorithm contains three kinds of parameters. This paper provides experimental results which show the algorithm to be stable for variations of parameters and give appropriate values for these parameters. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | meta-heuristics / inductive algorithm / abstraction / analogical reasoning / traveling salesman problem |
Paper # | AI97-4 |
Date of Issue |
Conference Information | |
Committee | AI |
---|---|
Conference Date | 1997/5/22(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Problem Solving based on the Control of Complexity : for Solving the Large Scale Traveling Salesman Problem |
Sub Title (in English) | |
Keyword(1) | meta-heuristics |
Keyword(2) | inductive algorithm |
Keyword(3) | abstraction |
Keyword(4) | analogical reasoning |
Keyword(5) | traveling salesman problem |
1st Author's Name | Seizaburo Niitsuma |
1st Author's Affiliation | Department of Systems Engineering, Faculty of Engineering, Shizuoka University() |
2nd Author's Name | Tsutomu Nakashima |
2nd Author's Affiliation | Department of Systems Engineering, Faculty of Engineering, Shizuoka University |
Date | 1997/5/22 |
Paper # | AI97-4 |
Volume (vol) | vol.97 |
Number (no) | 63 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |