Improving Performance of Heuristic Algorithms by Lebesgue Spectrum Filter

Mikio HASEGAWA  

Publication
IEICE TRANSACTIONS on Communications   Vol.E99-B   No.11   pp.2256-2262
Publication Date: 2016/11/01
Online ISSN: 1745-1345
Type of Manuscript: INVITED PAPER (Special Section on Deepening and Expanding of Information Network Science)
Category: 
Keyword: 
chaos,  combinatorial optimization,  lebesgue spectrum filter,  CDMA,  traveling salesman problema,  quadratic assignment problems,  

Full Text: FreePDF(687.2KB)


Summary: 
The previous researches on the chaotic CDMA have theoretically derived the chaotic sequences having the minimum asynchronous cross-correlation. To minimize the asynchronous cross-correlation, autocorrelation of each sequence have to be C(τ)≈C×rτ, r=-2+√3, dumped oscillation with increase of the lag τ. There are several methods to generate such sequences, using a chaotic map, using the Lebesgue spectrum filter (LSF) and so on. In this paper, such lowest cross-correlation found in the chaotic CDMA researches is applied to solution search algorithms for combinatorial optimization problems. In combinatorial optimization, effectiveness of the chaotic search has already been clarified. First, an importance of chaos and autocorrelation with dumped oscillation for combinatorial optimization is shown. Next, in order to realize ideal solution search, the LSF is applied to the Hopfield-Tank neural network, the 2-opt method and the 2-exchange method. Effectiveness of the LSF is clarified even for the large problems for the traveling salesman problems and the quadratic assignment problems.