臺灣博碩士論文加值系統

啟發式演算法藉由具意義的猜測，找尋可能得到最佳解的搜尋方向，進而提供求解複雜問題時，一個可行的方法。由於啟發式演算法只需花費極少的計算時間(相對於列舉出所有可行解的計算時間)，用以獲得一個近似解。因此，啟發式演算法似乎提供一個可行的研究方向，讓我們可以面對並解決複雜的問題。但在啟發式演算法的搜尋過程中，仍存有大量且多餘的計算。或者，我們可以說，啟發式演算法在求解的過程中，尚未完全的發揮其應有的效能。本論文提出一個簡單且有效的演算法，用以減少啟發式演算法的計算時間，同時嘗試維持或提升原有演算法之求解品質。這個新穎的演算法稱之被為樣式歸納法，其主要的概念是源自於我們觀察到，在啟發式演算法的收斂程序中，大部分的搜尋存在著重複的計算，且部分解的片段可以被視為最終結果的一部份。藉由移除這些計算，後續的收斂過程將可不需再次計算重複內容。本論文的主要目的不在於我們能夠節省多少的計算時間，而是在於如何減少多餘的計，使啟發式演算法不再浪費其計算能力。最後，根據我們的實驗結果顯示，樣式歸納法可以有效的節省計算時間，並同時維持求解品質。

Over the past three decades or so, metaheuristics has been one of the most important and successful techniques for finding the true or near optimal solution of complex problems. Instead of systematically enumerating and checking all the candidate solutions that would take
forever to accomplish, it works by guessing the right directions for finding the true or near optimal solution so that the space searched, and thus the time required, can be significantly reduced. However, our observation shows that most of the metaheuristic algorithms face a common problem. That is, because of the requirements of convergence, they all involve a lot of redundant computations during the convergence process. In this thesis, we present a simple but efficient algorithm for solving the problem, called the Pattern Reduction algorithm
(or PR for short). The proposed algorithm is motivated by the observation that some of the sub-solutions that are repeatedly computed during the convergence process can be considered as part of the final solutions and thus can be first compressed and then removed to eliminate
the redundant computations at the later iterations during the convergence process. Since PR is basically a concept that is not limited to any particular metaheuristic algorithm, we present several methods derived from the concept for eliminating the duplicate computations of metaheuristics in the thesis. Although our simulation results show that they all perform well in terms of the computation time reduced, they are not perfect in terms of the quality of the end results because in some cases they will cause a small loss of the quality. For this reason, rather than how much computation time the proposed algorithm can reduce, our ultimate
goal is to eliminate all the redundant computations while at the same time preserving or even enhancing the quality of the end result of metaheuristics alone.

List of Tables iv
List of Figures v
Acknowledgments vii
Chapter 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Chapter 2 Related Work 7
2.1 Combinatorial Optimization Problems . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Data Clustering Problem . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Single-Solution-Based Algorithms . . . . . . . . . . . . . . . . . . . 14
2.2.1.1 Simulated Annealing Algorithm . . . . . . . . . . . . . . . 15
2.2.1.2 Tabu Search Algorithm . . . . . . . . . . . . . . . . . . . 17
2.2.1.3 k-means Algorithm . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Population-Based Algorithms . . . . . . . . . . . . . . . . . . . . . 21
2.2.2.1 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2.2 Ant Colony Optimization . . . . . . . . . . . . . . . . . . 23
2.2.2.3 Particle Swarm Optimization . . . . . . . . . . . . . . . . 25
2.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Improving the Performance of Metaheuristics . . . . . . . . . . . . . . . . . 29
2.3.1 Initialization Methods . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 Local Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.3 Hybrid Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.4 Speedup Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 The Problems of Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.1 Diversity and Quality of the End Result . . . . . . . . . . . . . . . . 38
2.4.2 Convergence Speed and Computation Time . . . . . . . . . . . . . . 40
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Chapter 3 The Proposed Algorithm 44
3.1 The Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Assumptions and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 The Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.1 Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1.1 Time-Oriented . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1.2 Space-Oriented . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.1.3 Problem-Specific . . . . . . . . . . . . . . . . . . . . . . 56
3.3.1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.2 Compression and Removal . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.2.1 Lossy Method . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.2.2 Lossless Method . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.3 Initialization (Optional) . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.4 Multi-Start (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Chapter 4 Simulation Results 67
4.1 The Strategies of PR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.1 Time to Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.2 Removal Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 The Results of Traveling Salesman Problem . . . . . . . . . . . . . . . . . . 73
4.2.1 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 The Results of Data Clustering Problem . . . . . . . . . . . . . . . . . . . . 78
4.3.1 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Improving the Results of PR Enhanced Methods . . . . . . . . . . . . . . . . 82
4.4.1 The Results with Local Search . . . . . . . . . . . . . . . . . . . . . 82
4.4.2 The Results with Parallel Computing . . . . . . . . . . . . . . . . . 83
4.5 The Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.5.1 Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.5.2 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5.2.1 Time Complexity of k-means with PR . . . . . . . . . . . 90
4.5.2.2 Time Complexity of GA with PR . . . . . . . . . . . . . . 91
4.5.2.3 Time Complexity of Metaheuristics with PR . . . . . . . . 93
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Chapter 5 Conclusion and Future Work 95
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Adler, D. (1993). Genetic algorithms and simulated annealing: a marriage proposal. In
Proceedings of IEEE International Conference on Neural Networks, volume 2, pages 1104–
1109.
Ahuja, R. K., O‥ zlem Ergun, Orlin, J. B., and Punnen, A. P. (2002). A survey of very largescale
neighborhood search techniques. Discrete Applie Mathematics, 123(1-3):75–102.
Ambati, B. K., Ambati, J. ., and Mokhtar, M. M. (1991). Heuristic combinatorial optimization
by simulated darwinian evolution: a polynomial time algorithm for the traveling salesman
problem. Biological Cybernetics, 65:31–35.
Angeline, P. (1998). Evolutionary optimization versus particle swarm optimization: Philosophy
and performance differences. pages 601–610.
Baraglia, R., Hidalgo, J. I., and Perego, R. (2001). A hybrid heuristic for the traveling salesman
problem. IEEE Transactions on Evolutionary Computation, 5(6):613–622.
Barvinok, A. (2003). The geometric maximum traveling salesman problem. Journal of the
ACM, 50(5):641–664.
Berger, J. and Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing
problem with time windows. Computers and Operations Research, 31(12):2037–2053.
Blum, C. and Merkle, D., editors (2008). Swarm Intelligence: Introduction and Applications.
Natural Computing Series. Springer.
Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and
conceptual comparison. ACM Computing Surveys, 35(3):268–308.
Blum, C. and Roli, A. (2008). Hybrid metaheuristics: An introduction. In Hybrid Metaheuristics,
volume 114, pages 1–30. Springer.
Bonabeau, E., Dorigo, M., and Theraulaz, G. (1999). Swarm Intelligence: From Natural to
Artificial Systems. Oxford.
Bradley, P. S. and Fayyad, U. M. (1998). Refining initial points for k-means clustering. In
Proceedings of the International Conference on Machine Learning, pages 91–99.
Bui, T. N. and Moon, B. R. (1994). A fast and stable hybrid genetic algorithm for the ratiocut
partitioning problem on hypergraphs. In 31st Conference on Design Automation, pages
664–669.
Cant′u-Paz, E. (1998). A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux
et Systems Repartis, 10(2):141–171.
Cant′u-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic
Publishers, Norwell, MA, USA.
Cant′u-Paz, E. and Goldberg, D. E. (2000). Efficient parallel genetic algorithms: theory and
practice. Computer Methods in Applied Mechanics and Engineering, 186(2-4):221–238.
Cerny, V. (1985). A thermodynamical approach to the travelling salesman problem: an efficient
simulation algorithm. Journal of Optimization Theory and Applications, 45:41–51.
Chin, A. J., Kit, H. W., and Lim, A. (1999). A new GA approach for the vehicle routing
problem. In Proceedings of the IEEE International Conference on Tools with Artificial
Intelligence, pages 307–310.
Chu, S. C., Roddick, J. F., and Pan, J. S. (2004). Ant colony system with communication
strategies. Information Sciences, 167(1-4):63–76.
Clerc, M. and Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence
in a multidimensional complex space. IEEE Transactions on Evolutionary Computation,
6(1):58–73.
Cormen, T., Leiserson, C., and Rivest, R. (1990). Introduction to Algorithms. MIT Press.
Cotta, C., ghazali Talbi, E., and Alba, E. (2005). Parallel hybrid metaheuristics, pages 347–
370. John Wiley & Sons, Hoboken, N.J.
Das, S., Abraham, A., and Konar, A. (2008). Automatic kernel clustering with a multi-elitist
particle swarm optimization algorithm. Pattern Recognition Letters, 29(5):688–699.
Davis, L. (1985). Applying adaptive algorithms to epistatic domains. In Proceedings of the
International Joint Conference on Artificial Intelligence, pages 162–164.
Dawkins, R. (1989). The selfish gene. Oxford University Press, Oxford New York.
Day, W. (1992). Complexity theory: An introduction for practitioners of classification. In
Clustering and Classification, P. Arabie and L. Hubert, Eds. World Scientific Publishing
Co., Inc., River Edge, NJ.
Dorigo, M. and Gambardella, L. M. (1997). Ant colony system: A cooperative learning
approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation,
1(1):53–66.
Dorigo, M., Maniezzo, V., and Colorni, A. (1996). The ant system: Optimization by a colony
of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B,
26(1):29–41.
Dorigo, M. and St‥utzle, T. (2004). Ant Colony Optimization (Bradford Books). The MIT
Press.
Eberhart, R. C. and Shi, Y. (1998). Comparison between genetic algorithms and particle
swarm optimization. In Proceedings of the 7th International Conference on Evolutionary
Programming VII, pages 611–616, London, UK. Springer-Verlag.
Eberhart, R. C., Shi, Y., and Kennedy, J. (2001). Swarm Intelligence (The Morgan Kaufmann
Series in Artificial Intelligence). Morgan Kaufmann.
Ehrgott, M. and Gandibleux, X. (2000). A survey and annotated bibliography of multiobjective
combinatorial optimization. OR Spektrum, 22(4):425–460.
Elkan, C. (2003). Using the triangle inequality to accelerate k-means. In Proceedings of the
Twentieth International Conference on Machine Learning, pages 147–153.
Endoh, S., Toma, N., and Yamada (1998). Immune algorithm for n-tsp. In IEEE International
Conference on Systems, Man and Cybernetics, volume 4, pages 3844–3849.
Eschrich, S., Ke, J., Hall, L. O., and Goldgof, D. B. (2003). Fast accurate fuzzy clustering
through data reduction. IEEE Transactions on Fuzzy Systems, 11(2):262–270.
Ester, M., peter Kriegel, H., S, J., and Xu, X. (1996). A density-based algorithm for discovering
clusters in large spatial databases with noise. In Proceedings of International
Conference on Knowledge Discovery and Data Mining, pages 226–231.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal
of Global Optimization, 6(2):109–133.
Flood, M. M. (1955). The traveling salesman problem. Operation Research, 4:61–78.
Forrest, S. and Mitchell, M. (1993). Relative building-block fitness and the building-block
hypothesis. In Whitley, D. L., editor, Foundations of Genetic Algorithms 2, pages 109–126,
San Mateo, CA. Morgan Kaufmann.
Gambardella, L. M., Taillard, R., and Agazzi, G. (1999). MACS-VRPTW: A multiple ant
colony system for vehicle routing problems with time windows. In New Ideas in Optimization,
pages 63–76. McGraw-Hill.
Garey, M. and Johnson, D. (1979a). Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman and Company.
Garey, M. R. and Johnson, D. S. (1979b). Computers and Intractability : A Guide to the
Theory of NP-Completeness. W. H. Freeman & Co Ltd.
Geem, Z.W., Kim, J. H., and Loganathan, G. (2001). A new heuristic optimization algorithm:
Harmony search. SIMULATION, 76(2):60–68.
Gelenbe, E., Ghanwani, A., and Stinivasan, V. (1997). Improved neural heuristics for multicast
routing. IEEE Journal on Selected Areas in Communications, 15(2):147–155.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence.
Computers & Operations Research, 13(5):533–549.
Glover, F. (1989). Tabu search—part I. ORSA Journal on Computing, 1(3):190–206.
Glover, F. (1990). Tabu search—part II. ORSA Journal on Computing, 2(1):4–32.
Glover, F. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley Professional.
Goldberg, D. E., Deb, K., and Korb, D. (1990). An investigation of messy genetic algorithms.
Technical Report TCGA 90005, TCGA, University of Alabama, Tuscaloosa, Alabama.
Goldberg, D. E. and Richardson, J. (1987). Genetic algorithms with sharing for multimodal
function optimization. In Proceedings of the Second International Conference on Genetic
Algorithms on Genetic algorithms and their application, pages 41–49. L. Erlbaum Associates
Inc.
Grefenstette, J. J. (1993). Deception considered harmful. In Whitley, D. L., editor, Foundations
of Genetic Algorithms 2, pages 75–91, San Mateo, CA. Morgan Kaufmann.
Gr‥otschel, M., Lov′asz, L., and Schrijver, A. (1981). The ellipsoid method and its consequences
in combinatorial optimization. Combinatorica, 1(2):169–197.
Guha, S., Meyerson, A., Mishra, N., and Motwani, R. (2003). Clustering data streams: Theory
and practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):515–528.
Hammouda, K. M. and Kamel, M. S. (2004). Efficient phrase-based document indexing
for web document clustering. IEEE Transactions on Knowledge and Data Engineering,
16(10):1279–1296.
Hochbaum, D. S. and Shmoys, D. B. (1985). Using dual approximation algorithms for
scheduling problems: Theoretical and practical results. In Proceedings of the 26th Annual
Symposium on Foundations of Computer Science, pages 79–89.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. MIT Press, Boston, MA.
IRIS (1988). IRIS.
Jain, A., Murty, M., and Flynn, P. (1999). Data clustering: A review. ACM Computing
Surveys, 31(3).
Jain, A. K. and Dubes, R. C. (1988). Algorithms for clustering data. Prentice Hall, Englewood
Cliffs, NJ.
Jayalakshmi, G. A., Sathiamoorthy, S., and Rajaram, R. (2001). An hybrid genetic algorithm:
A new approach to solve traveling salesman problem. International Journal of Computational
Engineering Science, 2(2):339–355.
Jong, K. A. D. (1975). An analysis of the behavior of a class of genetic adaptive systems.
PhD thesis, Ann Arbor, MI, USA.
KDD (1998). KDD’98 dataset.
Kennedy, J. (2000). Stereotyping: improving particle swarm performance with cluster analysis.
In in Proceedings of the 2000 Congress on Evolutionary Computation, volume 2, pages
1507–1512.
Kennedy, J. and Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings of the
IEEE International Conference on Neural Networks, pages 1942–1948.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing.
Science, 220(4598):671–680.
Kogan, J. (2007). Introduction to Clustering Large and High-Dimensional Data. Cambridge
University Press, NY, USA.
Koza, J. R. (1992). Hierarchical automatic function definition in genetic programming. In
Foundations of Genetic Algorithms, pages 297–318.
Krishna, K. and Murty, M. N. (1999). Genetic k-means algorithm. IEEE Transactions on
System, Man and Cybernetics—Part B:Cybernetics, 29(3):433–439.
Kuo, R., Wang, H., Hu, T., and Chou, S.-H. (2005). Application of ant k-means on clustering
analysis. Computers & Mathematics with Applications, 50(10-12):1709–1724.
Laszio, M. and Mukherjee, S. (2006). A genetic algorithm using hyper-quadtrees for lowdimensional
k-means clustering. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 28(4):533–543.
Lawer, E. L., Lenstra, J. K., Kan, A. H. R., and D.B.Shmoys (1985). The Traveling Salesman
Problem. Wiley, New York, NY.
Lee, C. Y., Tsai, C.W., Chiang, M. C., and Yang, C. S. (2008). Fast VQ codebook generation
via pattern reduction. In Proceedings of the IEEE International Conference on Systems,
Man and Cybernetics, pages 256–261.
Lee, J. S., Oh, I. S., and Moon, B. R. (2004). Hybrid genetic algorithms for feature selection.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(11):1424–1437.
Liaw, C. F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European
Journal of Operational Research, 124(1):28–42.
Lin, F. T., Kao, C. Y., and Hsu, C. C. (1993). Applying the genetic approach to simulated
annealing in solving some NP-hard problems. IEEE Transactions on Systems, Man and
Cybernetics, 23(6):1752–1767.
Lin, S. and Kernighan, B. W. (1973a). An effective heuristic algorithm for the travelingsalesman
problem. Operations Research, 21(2):498–516.
Lin, S. and Kernighan, B.W. (1973b). An effective heuristic algorithm for traveling salesman
problem. Operation Research, 21:498–516.
Liu, B. (2007). Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data (Data-
Centric Systems and Applications). Springer.
Lloyd, S. (1982). Least Square Quantization in PCM. IEEE Transactions on Information
Theory, 28:129–137.
Lo, C. and Hus, C. (1998). Annealing framework with learning memory. IEEE Transactions
on Systems, Man and Cybernetics, Part A, 28(5):1–13.
Lobo, F. G., Goldberg, D. E., and Pelikan, M. (2000). Time complexity of genetic algorithms
on exponentially scaled problems. In Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO ’00), pages 151–158. ACM.
Lourenc﹐o, H. R., c. Martin, O., and St‥utzle, T. (2003). Iterated local search, in: Handbook of
Metaheuristics (Chapter 11). Springer.
Lu, Y., Lu, S., Fotouhi, F., Deng, Y., and Brown, S. J. (2004a). FGKA: A fast genetic k-means
clustering algorithm. Proceedings of Symposium on Applied Computing, pages 622–623.
Lu, Y., Lu, S., Fotouhi, F., Deng, Y., and Brown, S. J. (2004b). Incremental genetic k-means
algorithm and its application in gene expression data analysis. International Journal of
BMC Bioinformatics, 5(172).
Mahfoud, S. W. and Goldberg, D. E. (1995). Parallel recombinative simulated annealing: a
genetic algorithm. Parallel Computing, 21(1):1–28.
Man, K. F., Tang, K. S., and Kwong, S. (1999). Genetic Algorithms: Concepts and Designs.
Springer-Verlag, New York, Secaucus, NJ, USA.
Maniezzo, V. and Carbonaro, A. (1999). Ant colony optimization: An overview. In Essays
and Surveys in Metaheuristics, pages 21–44. Kluwer Academic Publishers.
Mart′ı, R. (1993). Multi-start methods. In Glover, F. W. and Kochenberger, G. A., editors,
Handbook of Metaheuristics, pages 355–368, Boston, MA. Kluwer Academic Publishers.
Martin, W. N., Barker, A. L., and Cohoon, J. P. (1999). Problem perturbation: Implications
on the fitness landscape. IEEE Congress on Evolutionary Computation, 1:744–751.
McQueen, J. B. (1967). Some methods of classification and analysis of multivariate observations.
In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and
Probability, pages 281–297.
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs.
Springer-Verlag, Berlin, Germany.
Michalski, R. S. (2000). Learnable evolution model: Evolutionary processes guided by machine
learning. Machine Learning, 38(1-2):9–40.
Misevicius, A. (2006). A fast hybrid genetic algorithm for the quadratic assignment problem.
In Proceedings of Genetic and evolutionary computation (GECCO ’06), pages 1257–1264.
ACM.
Montemanni, R., Gambardella, L. M., Rizzoli, A. E., and Donati, A. V. (2003). A new
algorithm for a dynamic vehicle routing problem based on ant colony system. In Second
International Workshop on Freight Transportation and Logistics, pages 27–30.
Moscato, P. (1999). New Ideas in Optimization, chapter Memetic Algorithms: A short introduction,
pages 219–234. McGraw-Hill, Maidenhead, UK, England.
M‥uhlenbein, H. (1989). Parallel genetic algorithms, population genetics and combinatorial
optimization. In Proceedings of the third international conference on Genetic algorithms,
pages 416–421, San Francisco, CA, USA.
Muhlenbein, H. and Paa, G. (1996). From recombination of genes to the estimation of distributions
i. binary parameters. In Parallel Problem Solving from Nature (PPSN), pages
178–187.
Nagata, Y. and Kobayashi, S. (1997). Edge Assembly Crossover: A high-power genetic
algorithm for the traveling salesman problem. In Proceedings of the 7th International
Conference on Genetic Algorithms, pages 450–457.
Nara, K. (1997). Genetic algorithm for power systems planning. volume 1, pages 60–65.
Ng, R. T. and Han, J. (2002). Clarans: A method for clustering objects for spatial data mining.
IEEE Transactions on Knowledge and Data Engineering, 14(5):1003–1016.
Nguyen, H. D., Yoshihara, I., Yamamori, K., and Yasunaga, M. (2007). Implementation of
an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on
Systems, Man, and Cybernetics, Part B, 37(1):92–99.
Omran, M. G., Engelbrecht, A. P., and Salman, A. A. (2005a). Particle swarm optimization
method for image clustering. International Journal of Pattern Recognition and Artificial
Intelligence, 19(3):297–321.
Omran, M. G. H., Engelbrecht, A. P., and Salman, A. (2005b). Dynamic clustering using
particle swarm optimization with application in image segmentation. In Prococeedings of
the 5th World Enformatika Conference, pages 332–344.
Ordonez, C. and Omiecinski, E. (2004). Efficient disk-based k-means clustering for relational
databases. IEEE Transactions on Knowledge and Data Engineering, 16(8):909–921.
Ouadfel, S. and Batouche, M. (2003). MRF-based image segmentation using ant colony
system. Electronic Letters on Computer Vision and Image Analysis,, 2(2):12–24.
Parsopoulos, K. E. and Vrahatis, M. N. (2002). Recent approaches to global optimization
problems through particle swarm optimization. Natural Computing, 1(2):235–306.
Pelleg, D. and Moore, A. W. (2000). x-means: Extending k-means with efficient estimation
of the number of clusters. In Proceedings of the Seventeenth International Conference on
Machine Learning, pages 727–734.
Pepper, J.W., Golden, B. L., andWasil, E. A. (2002). Solving the traveling salesman problem
with annealing-based heuristics: A computational study. IEEE Transactions on Systems,
Man and Cybernetics–Part A: Systems and Humans, 32(1):72–77.
Pham, D. T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., and Zaidi, M. (2005). The
bees algorithm. Technical report, Manufacturing Engineering Centre, Cardiff University,
Royaumes-Unis.
Pinto, D. and Bar′an, B. (2005). Solving multiobjective multicast routing problem with a new
ant colony optimization approach. In Proceedings of the 3rd international IFIP/ACM Latin
American conference on Networking, pages 11–19, New York, NY, USA. ACM.
Reeves, C. R., editor (1993). Modern heuristic techniques for combinatorial problems. John
Wiley & Sons, Inc., New York, NY, USA.
Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications,
volume 840. Springer-Verlag, Berlin Heidelberg, Heidelberg.
Reuters (1987). Reuters-21578 Text Categorization Collection.
Robbins, H. and Monro, S. (1951). A stochastic approximation method. The Annals of
Mathematical Statistics, 22(3):400–407.
Saatchi, S. and Hung, C. C. (2005). Hybridization of the ant colony optimization with the
k-means algorithm for clustering. In SCIA, volume 3540 of Lecture Notes in Computer
Science, pages 511–520. Springer.
Sch, B., o Smola, and uller, K. (1998). Nonlinear component analysis as a kernel eigenvalue
problem. Neural Computation, 10:1299–1319.
Schrijver, A. (2009). A course in combinatorial optimization.
Shi, Y. and Eberhart, R. C. (1998). Parameter selection in particle swarm optimization. In
Proceedings of the 7th International Conference on Evolutionary Programming VII, pages
591–600, London, UK. Springer-Verlag.
Shirai, H., Ishigame, A., Kawamoto, S., and Taniguchi, T. (1994). A solution of combinatorial
optimization problem by uniting genetic algorithms with hopfield’s model. IEEE
Computational Intelligence, 7:4704–4709.
Shmoys, D. B. (1995). Computing near-optimal solutions to combinatorial optimization problems.
In Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, pages 355–397. AMS Publications.
Sinha, A. and Goldberg, D. E. (2003). A survey of hybrid genetic and evolutionary algorithms.
IlliGAL Report No. 2003004, University of Illinois at Urbana-Champaign.
Steinhaus, H. (1956). Sur la division des corp materiels en parties. Bull. Acad. Polon. Sci,
1:801–804.
Stutzle, T. (1998). Parallelization strategies for ant colony optimization. In Proceedings of
PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, pages
722–731. Springer-Verlag.
Su, M. C. and Chang, H. T. (2000). Fast self-organizing feature map algorithm. IEEE Transactions
on Neural Networks, 11(3):721–733.
Sultan, A. B. M., Mahmod, R., Sulaiman, M. N., and Bakar, M. R. A. (2008). Selecting
quality initial random seed for metaheuristic approaches: A case of timetabling problem.
International Journal of the Computer, the Internet and Management, 16(1):38–45.
Talbi, E. G. (2002). A taxonomy of hybrid metaheuristics. Journal of Heuristics, 8(5):541–
564.
Ting, C. K. and Ko, C. F. (2008). Incorporating tabu search into the survivor selection of
genetic algorithm. In Proceedings of the IEEE International Conference on Systems, Man
and Cybernetics, pages 553–558.
Ting, C. K., Li, S. T., and Lee, C. (2001). TGA: a new integrated approach to evolutionary
algorithms. In Proceedings of the Congress on Evolutionary Computation, volume 2, pages
917–924.
Ting, C. K., Li, S. T., and Lee, C. (2003). On the harmonious mating strategy through tabu
search. Information Sciences, 156(3-4):189–214.
Tsai, C. F., Chen, Z. C., and Tsai, C. W. (2002a). MSGKA: An efficient clustering algorithm
for large databases. In Proceedings of the IEEE International Conference on Systems, Man
and Cybernetics, vol.5.
Tsai, C. F., Tsai, C. W., and Chen, C. P. (2004a). A novel algorithm for multimedia multicast
routing in a large scale network. Journal of Systems and Software, 72(3):431–441.
Tsai, C. F., Tsai, C. W., and Yang, T. (2002b). A modified multiple-searching method to genetic
algorithms for solving traveling salesman problem. In IEEE International Conference
on Systems, Man and Cybernetics, volume 3.
Tsai, C. W., Lee, C. Y., Chiang, M. C., and Yang, C. S. (2009a). A fast VQ codebook generation
algorithm via pattern reduction. Elsevier Pattern Recognition Letters, 30(7):653–660.
Tsai, C. W., Tseng, S. P., Chiang, M. C., and Yang, C. S. (2009b). A time-efficient method
for metaheuristics: Using tabu search and tabu GA as a case. In Proceedings of the Ninth
International Conference on Hybrid Intelligent Systems. (To appear).
Tsai, C. W., Yang, C. S., and Chiang, M. C. (2007). A novel pattern reduction algorithm
for k-means based clustering. In Proceedings of the IEEE International Conference on
Systems, Man and Cybernetics, pages 504–509.
Tsai, H. K., Yang, J. M., Tsai, Y. F., , and Kao, C. Y. (2004b). A serial population algorithm
for dynamic optimization problems. IEEE Transactions on System, Man, and Cybernetics–
Part B: Cybernetics, 34(4):1718–1729.
Tseng, L. Y. and Yang, S. B. (2000). A genetic clustering algorithm for data with nonspherical-
shape clusters. Pattern Recognition, 33(7):1251–1259.
Tseng, L. Y. and Yang, S. B. (2001). A genetic approach to the automatic clustering problem.
Pattern Recognition, 34(2):415–424.
Tseng, S. P., Tsai, C.W., Chiang, M. C., and Yang, C. S. (2008). Fast genetic algorithm based
on pattern reduction. In Proceedings of the IEEE International Conference on Systems,
Man and Cybernetics, pages 214–219.
UCI (1998). Synthetic Control Chart Time Series.
Universit‥at Heidelberg (1995). TSPLIB.
van der Merwe, D. W. and Engelbrecht, A. P. (2003). Data clustering using particle swarm
optimization. In The 2003 Congress on Evolutionary Computation, volume 1, pages 215–
220.
Vesanto, J. and Alhoniemi, E. (2000). Clustering of the self-organizing map. IEEE Transactions
on Neural Networks, 11(3):586–600.
Voudouris, C. and Tsang, E. P. K. (2003). Guided local search, in: Handbook of Metaheuristics
(Chapter 7). Springer.
Wang, L. and Jiao, L. (2000). A novel genetic algorithm based on immunity. IEEE Transactions
on Systems, Man, and Cybernetics—Part A: Systems and Humans, 30(5):552–561.
Wang, L., Maciejewski, A. A., Siegel, H. J., Roychowdhury, V. P., and Eldridge, B. D. (2005).
A study of five parallel approaches to a genetic algorithm for the traveling salesman problem.
Intelligent Automation and Soft Computing, 11(4):217–234.
Wang, W., Yang, J., and Muntz, R. (1997). STING: A statistical information grid approach
to spatial data mining. In Proceedings of Conference on Very Large Databases, pages
186–195.
Whitley, D., Starkweather, T., and Shaner, D. (1991). The traveling salesman and sequence
scheduling: Quality solutions using genetic edge recombination. In Handbook of Genetic
Algorithms, pages 350–372. Van Nostrand Reinhold, New York.
Xu, R. and II, D. W. (2005). Survey of clustering algorithms. IEEE Transaction on neural
netowrks, 16(3):645–678.
Xu, R. and Wunsch, D. C. (2008). Clustering. Wiley, John & Sons, Inc.
Yang, R. (1997). Solving large travelling salesman problems with small populations. pages
157–162.
Yoichi, T. and Nobuo, F. (1998). An improved genetic algorithm using the convex hull for
traveling salesman problem. In IEEE International Conference on Systems, Man and Cybernetics,
volume 3, pages 2279–2284.
Zhang, R. and Rudnicky, A. I. (2002). A large scale clustering scheme for kernel k-means.
16the International Conference on Pattern Recognition, 4:40289.
Zhang, T., Ramakrishnan, R., and Livny, M. (1996). BIRCH: an efficient data clustering
method for very large databases. In Proceedings of ACM SIGMOD international conference
on Management of data, pages 103–114.