TSP 문제를 해결하기위한 유전 알고리즘

1885 년에 다윈은 자연선택을 이용하여 종의 기원과 생물의 진화를 설명했다.

다윈의 자연선택학설은 세 가지 측면을 포함한다:

1920 년대에 일부 학자들은 통계생물학과 군유전학을 이용하여 다윈의 자연선택 이론을 다시 해석하여 현대의 종합 진화론을 형성했다.

인구 유전학은 다음과 같이 생각합니다:

유전 알고리즘에서 생물학과 관련된 개념 및 용어와 최적화 문제에 설명된 관계:

1960 년대 중반에 홀랜드는 비트 문자열 코딩 기술을 제안했습니다.

이 기술은 변이와 교차 작업에 적용되며 교차를 주요 유전 작업으로 강조합니다.

Holland 는 이 알고리즘을 자연 및 인공 시스템의 적응 행동 연구에 사용했으며, 1975 년 독창적인 저서' Adaptation Innatural and Artifical System' 을 발간했다.

그런 다음 알고리즘을 최적화 및 학습에 적용하고 이를 GA (유전 알고리즘) 라고 명명했습니다.

유전자 알고리즘의 기본 아이디어:

순서도:

가장 일반적으로 사용되는 정책: 경로 코딩

경로 내 도시의 위치를 직접 사용하여 최적화를 위한 상태를 구성합니다.

예: 구도시 TSP 문제, 경로: 5-4-1-7-9-8-6-2-3

경로 인코딩: (5 4 1 7 9 8 6 2 3)

입력:

10 도시 좌표는

(41,94); (37,84); (54,67); (25,62); (7,64); (2,99); (68,58); (71,44); (54,62); (83,69)

실행 결과:

파이썬 소스: /wangjiosw/GA-TSP

GA 는 다음과 같은 이점을 제공하는 범용 최적화 알고리즘입니다.

컴퓨터 기술이 발달하면서 GA 는 점점 더 주목을 받고 있으며 기계 학습, 패턴 인식, 이미지 처리, 신경망, 최적화 제어, 조합 최적화, VLSI 설계, 유전학 등의 분야에서 성공적으로 적용되었습니다.