유전 Algortihm - 가변 길이 최적화를위한 전략

Question

유전 알고리즘 (GA)을 사용하여 해결하고자하는 문제가 있습니다. 다음과 같은 문제를 단순화 할 수 있습니다 :

내가, 자동차 및 자동차 모델의 번호를 의미하는 회사의 자동차 풀을 최적화 할 수 있습니다. 나는 이미 Business car, transporter 또는 business car, business car, transporter와 같은 주어진 설정을 평가하는 fitness function calcFitness(carList)을 가지고있다. 이제 문제는 GA를 사용하여이 가변 길이 문제를 해결하는 방법입니다.

은 당신이 일반적으로 이러한 문제를 해결할 수있는 방법을 네 가지 아이디어를 가지고 (? 가능하다면 확실하지 않음) 아마 어떻게 든 가변 길이 염색체를 허용하는 GA를 구현

1. 단일 실행에 문제를 해결
2. 견적을 가능한 최대 자동차 수 (예 : 20)와 1에서 20 사이의 각 슬롯 번호에 대해 고정 길이의 GA를 실행하고 20 개의 결과를 비교하십시오.
3. # 2와 유사하지만 고정 된 상한선이없는 경우 : 1 차로 증가하고 슬롯 수가 증가하면 증가 된 숫자에 대한 최상의 해답이 이전의 것보다 나빠질 때까지 해결 방법 (그라데이션 기반의 접근 방식)
4. 두 누적 고정 길이 가스 : 부모 GA는 전적으로이 슬롯의 assignement을 최적화하는 또 다른 GA 자동차 슬롯과 운동 기능의 수를 최적화하기위한 책임이라고입니다

이러한 일반적인 접근 방식에 대해 어떻게 생각하십니까? 이러한 다양한 길이의 사례에 대한 다른 아이디어 또는 GA 대안이 있습니까?

Answer 1

가변 길이가 확실히 가능하며,이 문제를 가장 자연스럽게 표현한 것 같습니다. 왜 그것이 문제가됩니까? 유일한 실질적인 차이점은 교차 작업에 있습니다. 단일 점은 간단하지만 (a의 한 점을 선택하고 b의 점을 얻고 자동으로 가변 길이 자손을 얻음) 가변 길이의 직감을 필요로하는 연속적인 교차를하는 것이 더 좋습니다. 그러나 이는 나중에 철저한 테스트를 거쳐 구현 될 수 있습니다.

알고리즘을 사용하면 염색체가 좋을수록 더 나은 결과를 얻을 수 있습니다 (상황의 조합에 따라 다름). 유전자 프로그래밍과 같이 지수 함수가 팽창하지는 않습니다 (유전자형은 선형 서열보다는 나무 임). 그러나 여전히 염색체 길이가 불편하게 성장할 수 있습니다. 피트니스 기능에서이를 설명 할 필요가 있거나, 몇 가지 제한을 능가하는 후보자를 즉시 ​​거절하여 # 2와 같은 솔루션을 모델링 할 수 있습니다.