Share Email Print

Proceedings Paper

A rapid convergent genetic algorithm for NP-hard problems
Author(s): Liel Oren; Nonel Thirer
Format Member Price Non-Member Price
PDF $17.00 $21.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 10 May 2019
PDF: 10 pages
Proc. SPIE 11006, Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, 1100615 (10 May 2019); doi: 10.1117/12.2516766
Show Author Affiliations
Liel Oren, Holon Institute of Technology (Israel)
Nonel Thirer, Holon Institute of Technology (Israel)

Published in SPIE Proceedings Vol. 11006:
Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications
Tien Pham, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?