유전 알고리즘에서 토너먼트 선택의 여러 반복

Question

안녕하세요 여러분, 토너먼트 선택이 어떻게 여러 번 반복되는지에 대해 약간 혼란스럽습니다.

나는 당신이 무작위 쌍(또는 k 멤버)을 선택하고 승자를 짝짓기 풀에 넣기 시작한다는 것을 알고 있습니다.짝짓기 풀이 채워질 때까지 이 작업을 계속합니다.

그러나 나중에 무슨 일이 일어날지는 잘 모르겠습니다.

짝짓기 풀에 있는 것들과 무작위로 짝짓기를 시작할까요?그런 다음 새로운 세대에서 무작위 쌍을 선택하여 선택 프로세스를 다시 시작하시겠습니까?

감사해요.

Answer 1

전통적으로 토너먼트 우승자가 발견 된 후에 그들은 다음 세대를 형성합니다. 돌연변이, 선택 등의 모든 과정은 사이클 후에도 계속됩니다.

Answer 2

나는 동일한 코드를 반복해서 작성하지 않기 위한 프레임워크를 만들 정도로 이러한 일반 알고리즘을 꽤 많이 작성했습니다.

짝짓기 풀의 경우 찾고 있는 개체의 종류, 찾고 있는 솔루션에 따라 다르며, 개체를 결합할 수 있는 방법이 있는 경우 더 나은 개체를 생산할 가능성이 더 높습니다.

무작위 짝짓기를 사용할 수 있지만 이는 "더 나쁜" 해결책을 제공할 것입니다. 더 나은 개체를 생산할 것인지 여부를 모르기 때문에 더 나쁜 것입니다.그것은 여전히 ​​좋은 해결책이 될 것이며, 이 알고리즘을 작성하기 시작했을 때 나는 항상 무작위 짝짓기를 사용했지만, 2개의 오래된 것에서 새로운 개체를 얻은 직후에 3개의 성능을 비교하고 더 나쁜 것을 버리고 결국 부모 2명이서(1초짜리 자식을 버리고) 부모 1명과 자식 1명이 되는 경우도 있습니다.

그러나 더 효율적이려면 개인을 결합하여 더 나은 솔루션을 생성하는 방법을 알고 있는 경우(매우 까다로울 수 있음) 2명의 개인을 가져와 그들 사이의 선호도를 반환하는 선호도 함수를 사용할 수 있습니다.까다로운 부분은 선호도를 결정하는 것입니다.문제에 따라 매우 다를 수 있습니다.예를 들어, 여행하는 외판원 문제를 해결한다면 유사성이 낮은 개인을 짝짓을 때 가장 좋은 해결책을 얻을 수 있습니다.그래서 내 선호도 함수는 1 - 유사성을 반환했습니다.

이렇게 하면 반복 횟수를 80%까지 줄이고 매우 좋은 솔루션을 얻을 수 있었습니다.

그러나 풀이 클수록 선호도 함수를 실행하는 데 시간이 더 오래 걸린다는 점을 명심하세요. 선호도 함수는 O(n²) 또는 심지어 O(n³)일 수 있으며, 이 경우 알고리즘의 병목 현상이 발생할 수 있습니다.이런 경우에는 무작위 짝짓기를 사용하는 것이 더 나을 수 있습니다.

결론적으로, 무작위 교배는 좋습니다. 결국 실생활에서 이런 식으로 작동한다고 말할 수 있습니다. 하지만 두 개체 간의 친화력을 계산하는 방법을 안다면 이를 사용하여 반복 횟수를 줄일 수 있습니다. 좋은 해결책을 얻어야 합니다.컴퓨팅 친화력은 매우 복잡할 수 있다는 점을 명심하세요(그리고 주어진 풀에 대해 가장 좋은 친화력을 계산하는 것은 NP-Complete라고 추측하기도 합니다).

Answer 3

이것은 좋은 조언은 아니지만 ...

그러나 나중에 무슨 일이 일어나는지 잘 모르겠습니다.

하고 싶은대로하세요. 당신은 그것들을 모두 돌연변이 할 수 있습니다 ... 또는 토너먼트에서 선택한 각 쌍을 짝을 이룰 수 있습니다. 가장 잘 작동하는 것을 사용하십시오. 창의적입니다.

이 포럼의 다른 누군가가 지적했듯이 : 가스에 대한 더러운 작은 비밀은 그것이 과학보다 더 예술이라는 것입니다.

또한 진정으로 좋은 조언을 얻으려면 해결하려는 문제에 대한 더 나은 설명이 필요합니다.