Jun Sakuma
ABSTRACT
We propose a protocol for a local search and a genetic algorithm for the distributed traveling salesman problem (TSP). In the distributed TSP, information regarding the cost function such as traveling costs between cities and cities to be visited are separately possessed by distributed parties and both are kept private each other. We propose a protocol that securely solves the distributed TSP by means of a combination of genetic algorithms and a cryptographic technique, called the secure multiparty computation. The computation time required for the privacy preserving optimization is practical at some level even when the city-size is more than a thousand.
- Philip W. Blasmeier and Wendell J. Voisin, Supply Chain Management: A Time-Based Strategy, Industrial Management, September-October 1996, pp. 24--27, (1996).Google Scholar
- Robert B. Handfield and Ernest L. Nichols, Introduction to Supply Chain Management, Prentice Hall, 1st edition (1998).Google Scholar
- Andrew C.-C. Yao, Protocols for secure computation, Proc. of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 160--164 (1982).Google Scholar
- M.-C. Silaghi and D. Mitra, Distributed constraint satisfaction and optimization with privacy enforcement, Intelligent Agent Technology, pp, 531--535, (2004). Google ScholarDigital Library
- Koutarou Suzuki and Makoto Yokoo, Secure Generalized Vickrey Auction using Homomorphic Encryption, Seventh International Financial Cryptography Conference (FC-03) (2003).Google Scholar
- Kokoro Ikeda, Shigenobu Kobayashi, Deterministic Multi-step Crossover Fusion:A Handy Crossover for GAs, PPSN 7, pp. 162--171, (2002). Google ScholarDigital Library
- Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999, pp. 223--238, (1999). Google ScholarDigital Library
- Bart Goethals, Sven Laur, Helger Lipmaa and Taneli Mielikainen, On Private Scalar Product Computation for Privacy-Preserving Data Mining, 7th Int'l Conf. in Information Security and Cryptology (ICISC), vol. 3506 of LNCS, pp. 104--120, (2004). Google ScholarDigital Library
- S. Lin and B. Kernighan, Effective heuristic algorithm for the traveling salesman problem, Oper. Res., vol. 21, pp. 498--516, (1973).Google ScholarDigital Library
- Yuichi Nagata and Shigenobu Kobaayshi, Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem, 7th Int'l. Conf. on Genetic Algorithms, pp. 450--457, (1997).Google Scholar
- Goldreich, O., Foundations of Cryptography II: Basic Applications, Cambridge Univ Pr. (2004). Google ScholarDigital Library
- D. E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning, Addison Wesley, (1989). Google ScholarDigital Library
- D. Thierens and D. E. Goldberg, Elitist Recombination: an integrated selection recombination GA, First IEEE Congress on Evolutionary Computation, pp. 508--512 (1994).Google ScholarCross Ref
- H. Shimodaira, A Diversity Contral Oriented Genetic Algorithm (DCGA):Development and Experimental Results, Proc. of GECCO 1999, pp. 603--611 (1999).Google Scholar
Index Terms
- A genetic algorithm for privacy preserving combinatorial optimization
Recommendations
Hybrid Taguchi-genetic algorithm for global numerical optimization
In this paper, a hybrid Taguchi-genetic algorithm (HTGA) is proposed to solve global numerical optimization problems with continuous variables. The HTGA combines the traditional genetic algorithm (TGA), which has a powerful global exploration capability,...
Privacy-preserving distributed k-anonymity
DBSec'05: Proceedings of the 19th annual IFIP WG 11.3 working conference on Data and Applications Securityk-anonymity provides a measure of privacy protection by preventing re-identification of data to fewer than a group of k data items. While algorithms exist for producing k-anonymous data, the model has been that of a single source wanting to publish ...
Research on Path Optimization Based on Improved Adaptive Genetic Algorithm
IHMSC '15: Proceedings of the 2015 7th International Conference on Intelligent Human-Machine Systems and Cybernetics - Volume 01Path optimization, which can improve the travel efficiency of vehicle, has significances to time and cost saving. Path optimization mentioned in this article aims for optimizing total length and converts it into classical TSP to solve optimization ...
Comments