유전 알고리즘: 두 판 사이의 차이

유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이알고리즘이라기 아니며보다는 문제를 풀기 위한 접근방법에 가까우며, 문제를 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분의대부분 받아들일 수 있는 수준의 해를 보여줄 수 있다.

어떤 문제에 대해 유전자 형식이 정의되었다면, 어떤 해들의 유전자들을 서로 조합함으로써 기존의 해로부터 새로운 해를 만들어낼 수 있다. 이런 조합 연산은 교배(Crossover)에 비유할 수 있다. 우수한 해들을 선택하여 이들을 교배하면, 만들어진 해는 우수한 해들이 가지는 특성을 물려받을 가능성이 높을높게 것이다된다. 우수한 해의 선택에는 앞에서 정의한 적합도 함수를 이용할 수 있으며, 적합도가 높은 해가 선택될 확률을 높게 만들면, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 되고, 따라서 다음 세대의 해들은 최적해에 점차 가까워지게 된다. 또 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨주도록 할 수 있으며, 이는 [[지역 최적점]]에 빠지지 않도록 하는 주요한 기법이다.

일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법론이방법이 많이 사용된다. 이는 반대로 말하면, 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 준다고 볼 수 있다. 현 세대에서 가장 좋은 해라 할지라도 실제로는 지역 최적해에 가까운 해일 수도 있고, 반대로 좋지 않은 해라 할지라도 전역 최적해에는 더 가까울 수도 있기 때문이다. 실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로, 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적해에 빠지는 것을 가능한 한 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다.

교차·변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고, 기존 해 중 열등한 해를 가려내서 제외시키는 연산이다. 가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법(해집단의 다양성을 유지하기 위함) 등이 있다.

{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 각 해의 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다.

다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적선택확률적으로 선택한다. ([[룰렛 알고리즘]]이 자주 쓰인다)이다. 따라서 위의 예에서 적합도가 3인 (8,0,9)는 적합도가 6인 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 2번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8) , (9,0,9)로가 되며, 각각의 적합도는 5, 2가 된다.