A rapid  convergent genetic algorithm for NP-hard problems

Liel Oren; Nonel Thirer

doi:10.1117/12.2516766

10 May 2019 A rapid convergent genetic algorithm for NP-hard problems

Liel Oren, Nonel Thirer

Proceedings Volume 11006, Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications; 1100615 (2019) https://doi.org/10.1117/12.2516766
Event: SPIE Defense + Commercial Sensing, 2019, Baltimore, MD, United States

Abstract

This paper proposes a novel solution for the Traveling Salesman Problem, a NP (non-deterministic polynomial-time) hardness problem. The algorithm presented in this paper offers an innovative solution by combining the qualities of a Nearest Neighbor (NN) greedy algorithm and the Genetic Algorithm (GA), by overcoming their weaknesses. The paper analyses the algorithm features/improvements and presents this implementation on a FPGA based target board. The experimental results of the algorithm, tested in software (Matlab) and implemented on a portable hardware (FPGA for GA, Raspberry Pi 3 for NN) shows a significant improvement: a shorter route, compared to NN , a shorter running time (less generations) compared to traditional GA , and reaching the optimal minimum (validated by Matlab). In real time, the algorithm runs on a handheld console, which can also act as a server, through a custom Android client application.

Citation Download Citation

Liel Oren and Nonel Thirer "A rapid convergent genetic algorithm for NP-hard problems ", Proc. SPIE 11006, Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, 1100615 (10 May 2019); https://doi.org/10.1117/12.2516766

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available