유전 알고리즘

Genetic algorithm
2006년 NASA ST5 우주선 안테나.이 복잡한 모양은 최상의 방사선 패턴을 만들기 위한 진화적 컴퓨터 설계 프로그램에 의해 발견되었습니다.그것은 진화된 안테나로 알려져 있다.

컴퓨터 과학 및 운영 연구에서 유전 알고리즘(GA)은 진화 알고리즘(EA)의 더 큰 클래스에 속하는 자연 선택 과정에서 영감을 받은 메타 휴리스틱입니다.유전자 알고리즘은 돌연변이, 교차[1]선택같은 생물학적으로 영감을 받은 연산자에 의존하여 최적화검색 문제에 대한 고품질 솔루션을 생성하는 데 일반적으로 사용된다.GA 어플리케이션의 예로는 성능 향상을 위한 의사결정 트리 최적화, 스도쿠 [2]퍼즐 해결, 하이퍼 파라미터 최적화 등이 있습니다.

방법론

최적화 문제

유전 알고리즘에서 최적화 문제에 대한 후보 솔루션(개인, 생물, 유기체 또는 표현형이라고 함)의 집단은 더 나은 해결책으로 진화한다.각 후보 용액은 돌연변이 및 변형이 가능한 일련의 특성(염색체 또는 유전자형)을 가지고 있다.종래, 용액은 0과 1의 문자열로서 2진수로 나타내지만, 다른 인코딩도 가능하다.[3]

진화는 보통 무작위로 생성된 개인의 집단에서 시작되며, 세대라고 불리는 각 반복의 집단과 함께 반복적인 과정이다.각 세대에서 모집단의 모든 개인의 적합성이 평가된다. 적합성은 일반적으로 해결되는 최적화 문제에서 목적 함수의 값이다.더 건강한 개인은 현재 집단에서 확률적으로 선택되며, 각 개인의 게놈은 새로운 세대를 형성하기 위해 변형된다(재조합되고 랜덤하게 변형될 수 있다).그런 다음 새로운 세대의 후보 솔루션이 알고리즘의 다음 반복에서 사용됩니다.일반적으로 알고리즘은 최대 수의 세대가 생산되거나 모집단에 대해 만족스러운 적합 수준에 도달하면 종료된다.

일반적인 유전자 알고리즘에는 다음이 필요합니다.

  1. 유전적으로 표현된 솔루션 영역,
  2. 솔루션 영역을 평가하기 위한 적합성 함수입니다.

각 후보 솔루션의 표준 표현은 비트 배열(비트 세트 또는 비트 [3]문자열이라고도 함)입니다.다른 유형 및 구조의 배열도 기본적으로 동일한 방법으로 사용할 수 있습니다.이러한 유전자 표현을 편리하게 하는 주요 특성은 고정된 크기 때문에 부품이 쉽게 정렬되어 간단한 교차 작업이 용이하다는 것입니다.가변 길이 표현도 사용할 수 있지만 이 경우 크로스오버 구현이 더 복잡합니다.나무와 같은 표현은 유전자 프로그래밍에서 탐색되고 그래프 형태의 표현은 진화 프로그래밍에서 탐색된다. 선형 염색체와 나무의 혼합은 유전자 발현 프로그래밍에서 탐색된다.

일단 유전자 표현과 적합성 기능이 정의되면, GA는 해결책의 모집단을 초기화하고 돌연변이, 교차, 반전 및 선택 연산자의 반복적인 적용을 통해 개선한다.

초기화

모집단 크기는 문제의 성격에 따라 다르지만 일반적으로 수백 또는 수천 가지 가능한 해결책이 포함되어 있습니다.대부분의 경우 초기 모집단이 랜덤으로 생성되어 가능한 솔루션 전체 범위(검색 공간)가 허용됩니다.경우에 따라서는 최적의 솔루션을 찾을 수 있는 영역에 솔루션이 「시드」되는 일이 있습니다.

선택.

연속되는 세대마다 기존 인구의 일부를 선택하여 신세대를 육성한다.개별 솔루션은 피트니스 기반 프로세스를 통해 선택되며, 피트니스 기능에 의해 측정되는 피트니스 솔루션은 일반적으로 선택될 가능성이 높다.특정 선택 방법은 각 솔루션의 적합성을 평가하고 가장 적합한 솔루션을 우선적으로 선택합니다.다른 방법에서는 모집단의 랜덤 표본에만 등급을 매기는데, 이는 이전 공정에 시간이 많이 걸릴 수 있기 때문입니다.

적합성 기능은 유전적 표현에 대해 정의되며 제시된 솔루션의 품질을 측정합니다.피트니스 기능은 항상 문제에 의존합니다.예를 들어 배낭 문제에서는 일정한 용량의 배낭에 넣을 수 있는 객체의 총값을 최대화하려고 합니다.솔루션의 표현은 비트 배열일 수 있습니다.여기서 각 비트는 다른 객체를 나타내며 비트 값(0 또는 1)은 객체가 배낭에 있는지 여부를 나타냅니다.개체의 크기가 배낭 용량을 초과할 수 있으므로 이러한 표현이 모두 유효한 것은 아닙니다.솔루션의 적합성은 표현이 유효한 경우 배낭에 있는 모든 객체의 값 합계가 되고 그렇지 않은 경우 0이 됩니다.

어떤 문제에서는 적합성 표현을 정의하는 것이 어렵거나 심지어 불가능할 수 있다. 이러한 경우, 표현형의 적합성 함수 값을 결정하기 위해 시뮬레이션을 사용할 수 있다(예: 표현형으로 암호화된 형태를 가진 차량의 공기 저항을 결정하기 위해 계산 유체 역학을 사용함), 또는 심지어 대화형 유전 알고리즘도 다음과 같다.사용했다.

유전자 조작자

다음 단계는 유전자 연산자(교차(재조합이라고도 함)와 돌연변이)의 조합을 통해 선택된 사람들로부터 2세대 솔루션 집단을 생성하는 것이다.

생산되는 각 새로운 솔루션에 대해 앞에서 선택한 풀에서 번식하기 위해 한 쌍의 "부모" 솔루션이 선택됩니다.위의 교차 및 돌연변이 방법을 사용하여 "자녀" 솔루션을 생성함으로써 일반적으로 "부모"의 많은 특성을 공유하는 새로운 솔루션이 생성됩니다.새로운 자녀마다 새로운 부모가 선택되며, 적절한 크기의 새로운 솔루션 집단이 생성될 때까지 프로세스는 계속된다.비록 두 부모를 사용하는 것에 기반을 둔 생식 방법이 더 "생물학적 영감을 받은" 방법이지만, 일부[4][5] 연구는 두 명 이상의 "부모"가 더 높은 품질의 염색체를 생성한다고 시사한다.

이러한 과정은 궁극적으로 초기 세대와 다른 차세대 염색체 집단을 낳는다.일반적으로, 1세대의 가장 좋은 유기체만이 적은 비율의 덜 적합한 솔루션과 함께 번식을 위해 선택되기 때문에, 모집단에 대한 이 절차에 의해 평균 적합성이 증가할 것이다.이 덜 적합한 해결책은 부모의 유전자 풀 내에서 유전적 다양성을 보장하고 따라서 다음 세대의 아이들의 유전적 다양성을 보장한다.

교차 대 돌연변이의 중요성에 대해서는 의견이 분분하다.Fogel(2006)에는 돌연변이 기반 검색의 중요성을 뒷받침하는 많은 참고 문헌이 있다.

교차와 돌연변이가 주요 유전자 연산자로 알려져 있지만, [citation needed]유전자 알고리즘에서 재결집, 식민지화-멸종 또는 이동과 같은 다른 연산자를 사용할 수 있다.

작업 중인 문제 클래스에 대한 적절한 설정을 찾기 위해 변환 확률, 교차 확률 및 모집단 크기 등의 매개 변수를 조정할 필요가 있습니다.매우 작은 돌연변이율은 (본질이 비작동적인) 유전적 표류로 이어질 수 있다.재조합률이 너무 높으면 유전자 알고리즘의 조기 수렴을 초래할 수 있다.변이율이 너무 높으면 엘리트주의 선택을 사용하지 않는 한 좋은 용액이 손실될 수 있습니다.적절한 모집단 크기는 당면한 문제에 대한 충분한 유전적 다양성을 보장하지만, 필요한 값보다 큰 값으로 설정하면 계산 자원의 낭비를 초래할 수 있다.

휴리스틱스

위의 주요 연산자 외에 다른 경험적 통계학을 사용하여 계산을 더 빠르게 또는 더 견고하게 할 수 있습니다.사양 휴리스틱은 너무 유사한 후보 솔루션 간의 교차에 불이익을 줍니다. 이는 모집단의 다양성을 장려하고 최적의 [6][7]솔루션으로의 조기 수렴을 방지하는 데 도움이 됩니다.

종료

이 생성 프로세스는 종료 조건에 도달할 때까지 반복됩니다.일반적인 종료 조건은 다음과 같습니다.

  • 최소 기준을 충족하는 솔루션이 발견됨
  • 고정된 세대 수에 도달했습니다.
  • 할당된 예산(계산 시간/비용)에 도달했습니다.
  • 최고위 솔루션의 적합성은 계속적인 반복이 더 이상 더 나은 결과를 낳지 못할 정도로 높은 수준에 도달했거나 정체되어 있습니다.
  • 수작업 검사
  • 위의 조합

구성 요소 가설

유전자 알고리즘은 실행은 간단하지만 그 동작은 이해하기 어렵다.특히, 이러한 알고리즘이 실제 문제에 적용되었을 때 높은 적합도의 솔루션을 생성하는 데 자주 성공하는 이유를 이해하기 어렵다.빌딩 블록 가설(BBH)은 다음과 같이 구성됩니다.

  1. 평균 이상의 적합성을 가진 낮은 차수의 정의 길이 스키마타 등 "구성 요소"를 식별하고 재조합하여 적응을 수행하는 휴리스틱에 대한 설명입니다.
  2. 유전 알고리즘이 암묵적이고 효율적으로 이 휴리스틱을 구현함으로써 적응을 수행한다는 가설.

Goldberg는 휴리스틱에 대해 다음과 같이 설명합니다.

「짧고 낮은 순서, 높은 적합성의 스키마를 샘플링 해, 재조합(크로스 오버)해, 잠재적으로 높은 적합성의 문자열을 형성합니다.어떻게 보면, 이러한 특정의 스킴(구성 요소)을 사용하는 것으로, 문제의 복잡함을 경감할 수 있었습니다.모든 생각할 수 있는 조합에 의해서 고성능 스트링을 구축하는 것이 아니라, 과거의 샘플링의 최적인 부분 솔루션으로부터 보다 좋은 스트링을 구축할 수 있습니다.
유전자 알고리즘의 작용에 있어서 길이가 낮고 순서가 낮은 매우 적합한 스키마가 매우 중요한 역할을 하기 때문에 우리는 이미 그들에게 빌딩 블록이라는 특별한 이름을 붙였습니다.아이가 단순한 나무 블록을 배열하여 웅장한 요새를 만들듯이 유전 알고리즘도 짧은 것, 낮은 것, 고성능의 스키마타 또는 구성 [8]요소를 병치함으로써 최적의 성능을 추구합니다.

빌딩 블록 가설의 타당성에 대한 합의가 부족함에도 불구하고, 수년간 일관되게 평가되고 참조로 사용되어 왔다.예를 들어, 가설이 유지될 환경을 제공하기 위해 [9][10]분포 알고리즘의 많은 추정이 제안되었다.일부 등급의 문제에 대해 좋은 결과가 보고되었지만, GAs 효율성에 대한 설명으로서의 구성 블록 가설의 일반성 및/또는 실용성에 대한 회의론은 여전히 남아 있다.실제로 분포 [11][12][13]알고리즘의 추정 관점에서 그 한계를 이해하려는 작업이 상당히 많다.

제한 사항

대체 최적화 알고리즘에 비해 유전자 알고리즘 사용에는 다음과 같은 제한이 있습니다.

  • 복잡한 문제에 대한 반복적인 적합성 기능 평가는 종종 인공 진화 알고리즘의 가장 금지적이고 제한적인 세그먼트이다.복잡한 고차원, 멀티모달 문제에 대한 최적의 해결책을 찾기 위해서는 종종 매우 비싼 피트니스 기능 평가가 필요하다.구조 최적화 문제와 같은 실제 문제에서는 단일 기능 평가에 몇 시간에서 며칠의 완전한 시뮬레이션이 필요할 수 있습니다.일반적인 최적화 방법으로는 이러한 유형의 문제를 처리할 수 없습니다.이 경우 정확한 평가를 포기하고 계산적으로 효율적인 대략적인 적합성을 사용해야 할 수 있습니다.대략적인 모델의 결합은 복잡한 실제 생활 문제를 해결하기 위해 GA를 설득력 있게 사용하는 가장 유망한 접근법 중 하나일 수 있다.
  • 유전자 알고리즘은 복잡성과 함께 잘 확장되지 않는다.즉, 돌연변이에 노출된 요소의 수가 많은 경우 검색 공간의 크기가 기하급수적으로 증가합니다.이것은 엔진, 집 또는 비행기의[citation needed] 설계와 같은 문제에 이 기술을 사용하는 것을 극도로 어렵게 만든다.이러한 문제를 진화적 탐색으로 다루기 쉽게 만들기 위해서는 가능한 한 간단한 표현으로 세분화해야 한다.따라서 엔진 대신 팬 블레이드를 위한 설계를 코드하는 진화 알고리즘, 세부 건설 계획 대신 건물 모양, 항공기 설계 전체가 아닌 에어포일을 볼 수 있습니다.복잡성의 두 번째 문제는 좋은 해결책을 나타내도록 진화한 부품을 추가적인 파괴적 돌연변이로부터 보호하는 방법, 특히 적합성 평가에 다른 부품과 잘 결합해야 하는 경우이다.
  • "더 나은" 솔루션은 다른 솔루션과 비교해서만 제공됩니다.그 결과, 모든 문제에서 정지 기준이 명확하지 않습니다.
  • 많은 문제에서 GA는 문제의 전역 최적보다는 국소 최적점 또는 임의의 으로 수렴하는 경향이 있다.장기간의 건강을 위해 단기간의 건강을 희생하는 방법을 모른다는 뜻이다.이 발생 가능성은 피트니스 환경의 형상에 따라 달라집니다.특정 문제는 글로벌 최적화를 향한 쉬운 상승을 제공할 수 있고, 다른 문제는 기능이 국소 최적화를 찾기 쉽게 만들 수 있습니다. 문제는 다른 적합성 함수를 사용하거나 돌연변이율을 높이거나 다양한 솔루션 [14]집단을 유지하는 선택 기술을 사용함으로써 완화될 수 있다. 그러나 무상급식[15] 정리는 이 문제에 대한 일반적인 해결책이 없다는 것을 증명한다.다양성을 유지하기 위한 일반적인 기술은 "니체 패널티"를 부과하는 것이다.여기서 충분히 유사한 개인(니체 반경)의 그룹에는 패널티가 추가되어 후속 세대에서 해당 그룹의 대표성이 감소하여 다른(덜 유사한) 개인이 모집단에서 유지될 수 있게 된다.그러나 문제의 상황에 따라서는 이 방법이 효과적이지 않을 수 있습니다.다른 가능한 기술은 인구의 대부분이 서로 너무 유사할 때 인구의 일부를 무작위로 생성된 개인으로 단순히 대체하는 것이다.유전자 알고리즘(및 유전자 프로그래밍)에서 다양성은 중요하다. 왜냐하면 동종 집단을 넘나드는 것은 새로운 해결책을 낳지 않기 때문이다.진화 전략과 진화 프로그래밍에서는 돌연변이에 대한 의존도가 높기 때문에 다양성은 필수적이지 않다.
  • 게놈이 초기부터 향후 데이터에 더 이상 유효하지 않을 수 있는 해결책으로 수렴되기 시작함에 따라 동적 데이터 세트를 조작하는 것은 어렵습니다.용액의 품질이 떨어졌을 때 돌연변이의 확률을 높임으로써(유발 과변환이라고 함), 또는 때때로 유전자 풀에 완전히 새롭게 무작위로 생성된 요소들을 도입함으로써(랜덤 임팩트라고 함) 유전적 다양성을 증가시키고 조기 수렴을 방지함으로써 이것을 교정하기 위한 몇 가지 방법이 제안되었다.igrants)다시, 진화 전략과 진화 프로그래밍부모가 유지되지 않고 자식들 중에서만 새 부모를 선택하는 이른바 "코마 전략"으로 실행될 수 있다.이것은 동적 문제에 더 효과적일 수 있습니다.
  • GA는 해결책에 수렴할 방법이 없기 때문에(등반할 언덕이 없기 때문에) 적합성 측정이 단일의 올바른/잘못된 측정(결정 문제 등)인 문제를 효과적으로 해결할 수 없다.이 경우 랜덤 검색은 GA만큼 빠르게 솔루션을 찾을 수 있습니다.그러나 상황에 따라 성공/실패 시행을 반복하여 다른 결과를 얻을 수 있는 경우 성공 대 실패의 비율은 적절한 적합성 척도를 제공합니다.
  • 특정 최적화 문제와 문제 사례의 경우, 수렴 속도 측면에서 다른 최적화 알고리즘이 유전 알고리즘보다 더 효율적일 수 있다.대안 및 보완 알고리즘에는 진화 전략, 진화 프로그래밍, 시뮬레이션 어닐링, 가우스 적응, 언덕 오르기 및 군집 인텔리전스(예: 개미 군집 최적화, 입자 군집 최적화)와 정수 선형 프로그래밍에 기반한 방법이 포함됩니다.유전 알고리즘의 적합성은 문제의 지식의 양에 따라 달라집니다. 잘 알려진 문제는 종종 더 나은, 더 전문적인 접근방식을 가지고 있습니다.

변종

염색체 표현

가장 간단한 알고리즘은 각 염색체를 비트 문자열로 나타냅니다.일반적으로 숫자 파라미터는 정수로 나타낼 수 있지만 부동소수점 표현을 사용할 수도 있습니다.부동소수점 표현은 진화 전략진화 프로그래밍에서 자연스러운 것입니다.실가 유전 알고리즘의 개념은 제공되었지만 1970년대에 존 헨리 홀랜드에 의해 제안되었던 빌딩 블록 이론을 실제로 대표하지 않기 때문에 정말로 잘못된 명칭이다.그러나 이 이론은 이론적이고 실험적인 결과에 기초해 뒷받침이 없는 것은 아니다(아래 참조).기본 알고리즘은 비트레벨로 크로스오버와 변환을 수행합니다.다른 변형에서는 염색체를 명령 테이블, 링크된 목록의 노드, 해시, 객체 또는 기타 상상할 수 있는 데이터 구조의 색인인 숫자의 목록으로 취급합니다.데이터 요소 경계를 존중하도록 크로스오버 및 변환이 이루어진다.대부분의 데이터 유형에 대해 특정 변동 연산자를 설계할 수 있습니다.다른 염색체 데이터 유형은 다른 특정 문제 영역에 대해 더 잘 또는 더 나쁘게 작용하는 것으로 보인다.

정수의 비트 문자열 표현을 사용하는 경우 그레이 코딩이 사용되는 경우가 많습니다.이와 같이 정수의 작은 변화도 돌연변이 또는 크로스오버를 통해 쉽게 영향을 받을 수 있습니다.이것은 염색체를 더 나은 용액으로 바꾸기 위해 너무 많은 동시 돌연변이(또는 교차 이벤트)가 일어나야 하는 소위 해밍 벽에서 조기 수렴을 막는 데 도움이 되는 것으로 밝혀졌다.

다른 접근법은 염색체를 나타내기 위해 비트 문자열 대신 실제 값 숫자의 배열을 사용하는 것이다.스키마타 이론의 결과는 일반적으로 알파벳이 작을수록 더 좋은 성능을 보인다는 것을 암시하지만, 처음에는 실제 값 염색체를 사용함으로써 좋은 결과를 얻었다는 것이 연구자들에게는 놀라웠다.이는 유한한 염색체 모집단에서 부동소수점 [16][17]표현에서 예상하는 것보다 훨씬 낮은 카디널리티를 가진 가상 알파벳을 형성하는 실제 값 집합으로 설명되었다.

유전자 알고리즘에 접근할 수 있는 문제 영역의 확장은 여러 종류의 이종 부호화된 유전자를 하나의 염색체에 [18]연결함으로써 솔루션 풀의 보다 복잡한 부호화를 통해 얻을 수 있다.이 특정 접근방식을 통해 문제 파라미터에 대해 매우 상이한 정의 도메인을 필요로 하는 최적화 문제를 해결할 수 있습니다.예를 들어 캐스케이드 컨트롤러 튜닝의 문제에서 내부 루프 컨트롤러 구조는 3개의 파라미터의 기존 레귤레이터에 속할 수 있지만 외부 루프는 본질적으로 다른 설명을 가진 언어 컨트롤러(퍼지 시스템 등)를 구현할 수 있습니다.이 특정 형태의 부호화는 염색체를 섹션별로 재조합하는 특수한 교차 메커니즘을 필요로 하며, 복잡한 적응 시스템, 특히 진화 과정의 모델링과 시뮬레이션에 유용한 도구이다.

엘리트주의

새로운 집단을 구성하는 일반적인 과정의 실용적인 변형은 현재 세대에서 다음 세대로 변하지 않고 최고의 유기체가 계승될 수 있도록 하는 것이다.이 전략은 엘리트주의 선택으로 알려져 있으며 GA에 의해 얻어진 솔루션의 품질이 한 세대에서 다음 [19]세대로 저하되지 않음을 보증합니다.

병렬 구현

유전자 알고리즘의 병렬 구현은 두 가지 맛이 있습니다.거친 입자의 병렬 유전 알고리즘은 각 컴퓨터 노드의 모집단과 노드 간의 개체 이동을 가정한다.세분화된 병렬 유전 알고리즘은 각 프로세서 노드 상의 개인을 가정하여 선택 및 재생산을 위해 인접 개체와 함께 동작합니다.온라인 최적화 문제에 대한 유전자 알고리즘과 같은 다른 변형은 적합성 기능에 시간 의존성 또는 노이즈를 도입한다.

적응형 GA

적응형 매개 변수(적응형 유전 알고리즘, AGA)를 가진 유전 알고리즘은 유전 알고리즘의 또 다른 중요하고 유망한 변형이다.교차(pc)와 돌연변이(pm)의 확률은 유전 알고리즘이 얻을 수 있는 솔루션 정확도의 정도와 수렴 속도를 크게 결정한다.AGA는 pc와 pm의 고정값을 사용하는 것이 아니라 각 세대의 모집단 정보를 활용하여 pc와 pm을 적응적으로 조정하여 모집단의 다양성을 유지하고 수렴능력을 유지한다.적응형 유전 알고리즘(AGA)[20]에서 pc와 pm의 조정은 솔루션의 적합성 값에 따라 달라집니다.CAGA(clustering-based [21]adaptive genetic algorithm)에서는 모집단의 최적화 상태를 판단하기 위한 클러스터링 분석을 통해 pc와 pm의 조정은 이러한 최적화 상태에 따라 달라진다.GA를 다른 최적화 방법과 조합하면 매우 효과적일 수 있습니다.GA는 일반적으로 우수한 전역 솔루션을 찾는 데 매우 능숙한 경향이 있지만, 절대 최적화를 찾기 위해 마지막 몇 개의 돌연변이를 찾는 데는 매우 비효율적입니다.다른 기술(단순한 언덕 오르기 등)은 제한된 지역에서 절대 최적화를 찾는 데 매우 효율적입니다.GA와 힐 클라이밍을 번갈아 하면 힐 클라이밍의 견고성 결여를 극복하면서 GA의 효율성을[citation needed] 향상시킬 수 있습니다.

이것은 유전적 변이의 법칙이 자연적인 경우 다른 의미를 가질 수 있다는 것을 의미한다.예를 들어, 단계가 연속적으로 저장된다면, 교차하는 것은 모성 DNA의 여러 단계를 합산하여 부성 DNA의 여러 단계를 더하는 것일 수 있습니다.이것은 표현형 지형에서 능선을 따라갈 수 있는 벡터를 추가하는 것과 같습니다.따라서 공정의 효율은 여러 가지 크기만큼 증가할 수 있습니다.또한, 반전 연산자는 연속 순서 또는 생존 또는 [22]효율성을 위해 다른 적절한 순서를 배치할 수 있습니다.

개체군이 개별 구성원보다 전체적으로 진화되는 변이는 유전자 풀 재조합으로 알려져 있다.

높은 수준의 적합성 인식, 즉 솔루션의 적합성이 변수의 상호 작용 하위 집합으로 구성된 문제에 대해 GA의 성능을 개선하기 위해 많은 변형이 개발되었다.이러한 알고리즘은 이러한 유익한 표현형 상호작용을 학습하는 것을 목표로 한다.따라서 이러한 가설은 파괴적 재조합을 적응적으로 감소시키는 데 있어 빌딩 블록 가설과 일치합니다.이 접근방식의 대표적인 예로는 mGA,[23] GEMGA[24] [25]및 LLGA가 있습니다.

문제 도메인

유전 알고리즘에 의한 해결책에 특히 적합한 것으로 보이는 문제에는 시간표 설정스케줄링 문제가 있으며, 많은 스케줄링 소프트웨어 패키지는 GA에[citation needed] 기반하고 있다. [26]GA는 엔지니어링에도 적용되어 왔다.유전자 알고리즘은 종종 글로벌 최적화 문제를 해결하기 위한 접근법으로 적용된다.

일반적인 경험적 법칙으로, 혼합, 즉 교차와 결합된 돌연변이전통적인 언덕 오르기 알고리즘이 고착될 수 있는 국소 최적에서 모집단을 이동시키도록 설계되었기 때문에 복잡한 적합성 지형을 가진 문제 영역에서 유용할 수 있다.일반적으로 사용되는 교차 연산자는 균일한 모집단을 변경할 수 없습니다.돌연변이만으로도 (마르코프 연쇄보이는) 전체적인 유전 알고리즘 과정의 에르고디스를 제공할 수 있다.

유전 알고리즘에 의해 해결되는 문제의 예로는 태양광을 [27]집열기에 흘려보낼 수 있도록 설계된 거울, 우주에서 [28]무선 신호를 수신하도록 설계된 안테나, 컴퓨터 [29]수치를 위한 보행 방법, 복잡한 흐름장에서의[30] 공기역학적 물체의 최적 설계 등이 있다.

알고리즘 설계 매뉴얼에서 Skiena는 모든 작업에 대해 유전 알고리즘을 사용하지 말 것을 조언합니다.

[I]t는 돌연변이 및 비트 문자열의 교차와 같은 유전자 연산자의 관점에서 응용 프로그램을 모델링하는 것은 매우 부자연스럽다.의사생물학은 당신과 당신의 문제 사이에 또 다른 차원의 복잡성을 더합니다.둘째, 유전자 알고리즘은 사소한 문제에는 매우 오랜 시간이 걸린다.[...]진화와의 유추는 매우 적절할 수 있다.[...] 상당한 진보는 수백만 년을 필요로 한다.

[...]

유전자 알고리즘이 올바른 공격 방법이라고 생각되는 문제를 만난 적이 없습니다.또, 유전자 알고리즘을 사용해 보고되는 계산 결과가, 좋은 인상을 남긴 것은 본 적이 없습니다.부두교에서 필요로 하는 휴리스틱한 검색을 위해 시뮬레이트된 어닐링을 계속하십시오.

--

역사

1950년, 앨런 튜링은 [32]진화의 원리를 병렬로 하는 "학습 기계"를 제안했다.진화에 대한 컴퓨터 시뮬레이션은 1954년 [33][34]뉴저지 프린스턴 고등연구소에서 컴퓨터를 사용하던 닐스바리첼리의 연구로 시작되었다.그의 1954년 출판물은 널리 주목받지 못했다.1957년부터,[35] 호주의 정량 유전학자 알렉스 프레이저는 측정 가능한 특성을 조절하는 여러 개의 위치를 가진 유기체의 인위적인 선택 시뮬레이션에 대한 일련의 논문을 발표했다.이러한 시작부터, 생물학자들에 의한 진화의 컴퓨터 시뮬레이션은 1960년대 초에 더욱 보편화되었고, 그 방법은 프레이저와 버넬(1970)[36]과 크로스비(1973)[37]의 책에 기술되었다.프레이저의 시뮬레이션은 현대 유전 알고리즘의 모든 필수 요소를 포함했다.또한 Hans-Joachim Bremermann은 1960년대에 최적화 문제에 대한 솔루션 집단을 채택하여 재조합, 돌연변이 및 선택을 수행하는 일련의 논문을 발표했습니다.Bremermann의 연구는 [38]또한 현대 유전 알고리즘의 요소들을 포함했다.다른 주목할 만한 초기 개척자들로는 리처드 프리드버그, 조지 프리드먼, 마이클 콘래드가 있다.많은 초기 논문들이 포겔(1998)[39]에 의해 전재되었다.

비록 크기입니다 Barricelli, 일에서 그가 1963년에 보도했다, 능력 – Rechenberg의 그룹 복잡한 공학 문제를 해결할 수 있었다만이 널리 알려져 있는 최적화 방법 인고 Rechenberg과 Hans-Paul Schwefel의 1960년대 작품과 1970년대 초의 결과로 단순한 game,[40]인공적으로 진화를 연출하기 진화 시뮬레이션을 했다.s가 현장 흙대략적인 진화 [41][42][43][44]전략 다른 접근법은 인공지능을 생성하기 위해 제안된 로렌스 포겔의 진화적 프로그래밍 기법이다.진화 프로그래밍은 원래 환경을 예측하기 위해 유한 상태 기계를 사용했으며 예측 로직을 최적화하기 위해 변동과 선택을 사용했습니다.특히 유전 알고리즘은 1970년대 초 John Holland의 연구, 특히 그의 책 Adaptation in Natural and Artificial Systems(1975)를 통해 인기를 끌었다.그의 연구는 미시간 대학의 Holland와 그의 학생들에 의해 수행된 세포 자동화에 대한 연구로 시작되었다.Holland는 Holland's Schema 정리로 알려진 다음 세대의 품질을 예측하기 위한 공식화된 프레임워크를 도입했습니다.GA의 연구는 1980년대 중반 펜실베니아 피츠버그에서 제1회 유전 알고리즘 국제 회의가 열리기 전까지 대체로 이론적으로 남아 있었다.

시판 제품

1980년대 후반, General Electric은 세계 최초의 유전자 알고리즘 제품인 산업 [45][circular reference]프로세스용으로 설계된 메인프레임 기반 툴킷을 판매하기 시작했습니다.1989년 액셀리스는 세계 최초의 데스크톱 컴퓨터용 상용 GA 제품인 Evolver를 출시했다.뉴욕타임스 테크놀로지 작가마코프[46] 1990년에 에볼버에 대해 썼고,[47] 1995년까지 유일한 대화형 상업 유전 알고리즘으로 남아있었다.에볼버는 1997년에 팰리세이드에 매각되어 여러 언어로 번역되어 현재 6번째 [48]버전이다.1990년대 이후 MATLAB은 3개의 무파생 최적화 휴리스틱 알고리즘(시뮬레이션 어닐링, 입자 군집 최적화, 유전 알고리즘)과 2개의 직접 검색 알고리즘(단순 검색, 패턴 검색)[49]을 구축했다.

관련 기술

부모 필드

유전 알고리즘은 하위 분야입니다.

관련 필드

진화 알고리즘

진화 알고리즘은 진화 컴퓨팅의 하위 분야입니다.

  • 진화 전략(ES, Rechenberg, 1994 참조)은 돌연변이와 중간 또는 이산 재조합을 통해 개인을 진화시킨다.ES 알고리즘은 특히 실제 가치 [50]영역의 문제를 해결하기 위해 설계되었습니다.자체 적응을 사용하여 검색의 제어 매개 변수를 조정합니다.자가 적응의 비랜덤화는 현대의 공분산 행렬 적응 진화 전략(CMA-ES)으로 이어졌다.
  • 진화 프로그래밍(EP)은 주로 돌연변이와 선택 및 임의 표현을 가진 솔루션 집단을 포함합니다.자가 적응을 사용하여 매개변수를 조정하고, 여러 부모로부터 받은 정보 결합과 같은 다른 변동 연산을 포함할 수 있습니다.
  • 분포 알고리즘 추정(EDA)은 기존 재현 연산자를 모델 유도 연산자로 대체합니다.그러한 모델은 기계 학습 기술을 사용하여 모집단에서 학습되며, 새로운 솔루션을 추출하거나[51][52] [53]교차 유도에서 생성할 수 있는 확률론적 그래픽 모델로 표현된다.
  • 유전자 프로그래밍(GP)은 John Koza에 의해 널리 보급된 관련 기술로 함수 매개 변수가 아닌 컴퓨터 프로그램이 최적화된다.유전자 프로그래밍은 종종 유전자 알고리즘의 전형적인 목록 구조 대신 나무 기반의 내부 데이터 구조를 사용하여 적응을 위한 컴퓨터 프로그램을 나타냅니다.유전 프로그래밍에는 데카르트 유전 프로그래밍, 유전자 발현 프로그래밍,[54] 문법 진화, 선형 유전 프로그래밍, 다중 표현 프로그래밍많은 변형이 있습니다.
  • 그룹화 유전 알고리즘(GGA)은 GA의 진화로서, 기존의 GA와 같은 개별 항목에서 항목의 [55]그룹 또는 하위 집합으로 초점이 이동한다.Emanuel Falkenauer가 제안한 이러한 GA 진화 이면의 아이디어는 일련의 아이템이 최적의 방법으로 분리된 아이템 그룹으로 분할되어야 하는 몇 가지 복잡한 문제, 즉 군집화 또는 분할 문제를 해결하는 것이 유전자와 동등한 아이템 그룹의 특성을 만들어 더 잘 달성될 것이라는 것이다.이러한 문제에는 빈 패킹, 라인 밸런싱, 거리 측정과 관련된 클러스터링, 균일한 파일 등이 있으며, 기존 GA의 성능이 저조하다는 것이 입증되었습니다.유전자를 그룹과 동등하게 만드는 것은 일반적으로 가변적인 길이의 염색체와 전체 항목의 그룹을 조작하는 특별한 유전 연산자를 의미한다.특히 빈 패킹의 경우, Martello와 Toth의 우성 기준과 교배된 GGA는 현재까지 가장 좋은 기술이다.
  • 대화형 진화 알고리즘은 인간의 평가를 사용하는 진화 알고리즘입니다.일반적으로 사용자의 미적 취향에 맞게 진화하는 이미지, 음악, 예술적 디자인 및 형태 등 컴퓨터 피트니스 기능을 설계하기 어려운 영역에 적용됩니다.

군집 지능

군집 지능은 진화 컴퓨팅의 하위 분야입니다.

  • 개미 군집 최적화(ACO)는 페로몬 모델을 갖춘 많은 개미(또는 에이전트)를 사용하여 솔루션 공간을 횡단하고 국소적으로 생산 가능한 영역을 찾습니다.
  • 분포 [56]알고리즘의 추정으로 간주되지만, 입자 군집 최적화(PSO)는 모집단 기반 접근법을 사용하는 다중 매개변수 최적화를 위한 계산 방법이다.후보 솔루션(입자)의 집단(군)이 서치 공간에서 이동하며, 입자의 이동은 자신의 가장 잘 알려진 위치와 군집 전체의 가장 잘 알려진 위치 모두에 의해 영향을 받는다.유전 알고리즘과 마찬가지로 PSO 방법은 모집단 구성원 간의 정보 공유에 의존합니다.일부 문제에서는 PSO가 GA보다 계산적으로 더 효율적이며, 특히 연속 변수의 제약 [57]없는 문제에서는 더욱 효율적입니다.

기타 진화적 컴퓨팅 알고리즘

진화 계산은 메타 휴리스틱 방법의 하위 필드입니다.

  • Memetic Algorithm(MA;메트릭 알고리즘)은 다른 것들과 마찬가지로 하이브리드 유전 알고리즘이라고 불리며, 솔루션이 국소적인 개선 국면의 대상이 되는 모집단 기반 방법입니다.밈 알고리즘의 개념은 유전자와 달리 스스로 적응할 수 있는 밈에서 비롯됩니다.일부 문제 영역에서는 기존 진화 알고리즘보다 더 효율적인 것으로 나타났습니다.
  • 진화 생태학, 특히 세균학적 적응에서 영감을 얻은 세균학적 알고리즘(BA).진화생태학은 생물들이 어떻게 적응하는지를 발견하기 위한 목적으로 그들의 환경의 맥락에서 생물들을 연구하는 학문이다.그 기본 개념은 이기종 환경에서는 전체 환경에 적합한 개인이 한 명도 없다는 것입니다.따라서 인구 수준에서 추론할 필요가 있다.또한 복잡한 위치 설정 문제(휴대전화용 안테나, 도시계획 등)나 데이터 [58]마이닝에도 BA를 성공적으로 적용할 수 있을 것으로 생각된다.
  • 문화 알고리즘(CA)은 유전 알고리즘과 거의 동일한 모집단 구성 요소와 더불어 믿음 공간이라고 불리는 지식 구성 요소로 구성됩니다.
  • 초유기체의 [59]이동에서 영감을 얻은 차등 진화(DE).
  • 가우스 적응(정상적 또는 자연적 적응, GA와의 혼동을 피하기 위한 약어 NA)은 신호 처리 시스템의 제조 수율을 극대화하기 위한 것이다.일반적인 파라메트릭 최적화에도 사용할 수 있습니다.그것은 수용성의 모든 영역과 모든 가우스 분포에 유효한 특정한 정리에 의존한다.NA의 효율성은 정보 이론과 효율의 일정한 정리에 의존한다.그 효율성은 정보를 [60]얻는 데 필요한 작업으로 나눈 정보로 정의됩니다.NA는 개인의 피트니스보다는 평균 피트니스를 최대화하기 때문에 피크 사이의 계곡이 사라질 수 있도록 경치가 평탄해진다.따라서 피트니스 풍경에서 국지적인 피크를 피하기 위한 특정한 "환경"이 있습니다.NA는 평균 적합도를 일정하게 유지하는 동시에 가우스의 무질서(평균 정보)를 극대화할 수 있기 때문에 모멘트 매트릭스의 적응에 의한 첨단을 오르는 데도 능숙하다.

기타 메타 휴리스틱 메서드

메타휴리스틱 방법은 확률적 최적화 방법에 광범위하게 포함된다.

  • Simulated Annealing(SA; 시뮬레이션 어닐링)은 개별 솔루션에서 랜덤 돌연변이를 테스트하여 검색 공간을 횡단하는 관련 글로벌 최적화 기술입니다.체력을 높이는 돌연변이는 항상 허용된다.적합도를 낮추는 돌연변이는 적합도의 차이와 온도 감소 모수를 기반으로 확률적으로 허용됩니다.SA의 용어로, 사람들은 최고의 체력 대신에 가장 낮은 에너지를 찾는 것을 말한다.SA는 표준 GA 알고리즘 내에서 비교적 높은 돌연변이율로 시작하여 일정대로 시간이 지남에 따라 감소시킴으로써 사용할 수도 있습니다.
  • Tabu 검색(TS)은 둘 다 개별 솔루션의 돌연변이를 테스트하여 솔루션 공간을 이동한다는 점에서 시뮬레이션 어닐링과 유사합니다.시뮬레이트된 어닐링은 하나의 변이 솔루션만 생성하는 반면, tabu 검색은 많은 변이 솔루션을 생성하고 생성된 솔루션 중 가장 낮은 에너지로 솔루션으로 이동합니다.솔루션 공간의 순환을 방지하고 이동을 촉진하기 위해 일부 솔루션 또는 전체 솔루션 목록을 유지합니다.솔루션이 솔루션 공간을 통과할 때 업데이트되는 tabu 목록의 요소를 포함하는 솔루션으로 이동하는 것은 금지됩니다.
  • 극단적 최적화(EO) 후보 솔루션 집단과 함께 작동하는 GA와 달리 EO는 단일 솔루션을 발전시키고 최악의 컴포넌트를 로컬로 수정합니다.이를 위해서는 개별 솔루션 구성요소에 품질 측정("적합성")을 할당할 수 있는 적절한 표현을 선택해야 합니다.이 알고리즘의 지배원칙은 저품질 구성요소를 선택적으로 제거하고 무작위로 선택된 구성요소로 대체함으로써 긴급한 개선이다.이는 더 나은 솔루션을 만들기 위해 우수한 솔루션을 선택하는 GA와 분명히 상충됩니다.

기타 확률적 최적화 방법

  • 교차 엔트로피(CE) 방법은 모수화된 확률 분포를 통해 후보 솔루션을 생성합니다.매개 변수는 다음 반복에서 더 나은 샘플을 생성하기 위해 교차 엔트로피 최소화를 통해 업데이트됩니다.
  • RSO(Reactive Search Optimization)는 하위 기호 기계 학습 기술을 검색 휴리스틱스에 통합하여 복잡한 최적화 문제를 해결합니다.reactive라는 단어는 중요한 파라미터의 자가조정을 위한 내부 온라인 피드백 루프를 통해 검색 중 이벤트에 대한 즉각적인 응답을 암시합니다.Reactive Search의 관심 방법론에는 기계 학습과 통계, 특히 강화 학습, 활성 또는 쿼리 학습, 신경 네트워크 및 메타 휴리스틱스가 포함됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 미첼 1996, 페이지 2
  2. ^ Gerges, Firas; Zouein, Germain; Azar, Danielle (12 March 2018). "Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles". Proceedings of the 2018 International Conference on Computing and Artificial Intelligence. ICCAI 2018. New York, NY, USA: Association for Computing Machinery: 19–22. doi:10.1145/3194452.3194463. ISBN 978-1-4503-6419-5. S2CID 44152535.
  3. ^ a b 휘틀리 1994, 페이지 66
  4. ^ 에이벤, A. E. 외 연구진(1994)"다부모 재조합 유전자 알고리즘"PPSN III: 진화 계산에 관한 국제 회의의 진행.제3회 자연병렬문제해결회의: 78~87.ISBN 3-540-58484-6.
  5. ^ Ting, Chuan-Kang (2005년)."선택 없는 다부모 유전 알고리즘의 평균 수렴 시간에 대하여"인공생명체의 진보: 403–412.ISBN 978-3-540-28848-0.
  6. ^ Deb, Kalyanmoy; Spears, William M. (1997). "C6.2: Speciation methods". Handbook of Evolutionary Computation. Institute of Physics Publishing. S2CID 3547258.
  7. ^ Shir, Ofer M. (2012). "Niching in Evolutionary Algorithms". In Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.). Handbook of Natural Computing. Springer Berlin Heidelberg. pp. 1035–1069. doi:10.1007/978-3-540-92910-9_32. ISBN 9783540929093.
  8. ^ 골드버그 1989, 페이지 41
  9. ^ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1 January 2006). Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA). Scalable Optimization Via Probabilistic Modeling. Studies in Computational Intelligence. Vol. 33. pp. 39–61. doi:10.1007/978-3-540-34954-9_3. ISBN 978-3-540-34953-2.
  10. ^ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1 January 1999). BOA: The Bayesian Optimization Algorithm. Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1. Gecco'99. pp. 525–532. ISBN 9781558606111.
  11. ^ Coffin, David; Smith, Robert E. (1 January 2008). Linkage Learning in Estimation of Distribution Algorithms. Linkage in Evolutionary Computation. Studies in Computational Intelligence. Vol. 157. pp. 141–156. doi:10.1007/978-3-540-85068-7_7. ISBN 978-3-540-85067-0.
  12. ^ Echegoyen, Carlos; Mendiburu, Alexander; Santana, Roberto; Lozano, Jose A. (8 November 2012). "On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms". Evolutionary Computation. 21 (3): 471–495. doi:10.1162/EVCO_a_00095. ISSN 1063-6560. PMID 23136917. S2CID 26585053.
  13. ^ Sadowski, Krzysztof L.; Bosman, Peter A.N.; Thierens, Dirk (1 January 2013). On the Usefulness of Linkage Processing for Solving MAX-SAT. Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. Gecco '13. pp. 853–860. doi:10.1145/2463372.2463474. hdl:1874/290291. ISBN 9781450319638. S2CID 9986768.
  14. ^ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19 November 2012). "An efficient algorithm for function optimization: modified stem cells algorithm". Central European Journal of Engineering. 3 (1): 36–50. doi:10.2478/s13531-012-0047-8.
  15. ^ 울퍼트, D.H., 맥레디, W.G., 1995.최적화를 위한 무료 점심 이론이 없습니다.싼타페 연구소, SFI-TR-05-010, 싼타페.
  16. ^ Goldberg, David E. (1991). "The theory of virtual alphabets". Parallel Problem Solving from Nature. Parallel Problem Solving from Nature, Lecture Notes in Computer Science. Lecture Notes in Computer Science. Vol. 496. pp. 13–22. doi:10.1007/BFb0029726. ISBN 978-3-540-54148-6.
  17. ^ Janikow, C. Z.; Michalewicz, Z. (1991). "An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms" (PDF). Proceedings of the Fourth International Conference on Genetic Algorithms: 31–36. Retrieved 2 July 2013.
  18. ^ Patrascu, M.; Stancu, A.F.; Pop, F. (2014). "HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation". Soft Computing. 18 (12): 2565–2576. doi:10.1007/s00500-014-1401-y. S2CID 29821873.
  19. ^ Baluja, Shumeet; Caruana, Rich (1995). Removing the genetics from the standard genetic algorithm (PDF). ICML.
  20. ^ Srinivas, M.; Patnaik, L. (1994). "Adaptive probabilities of crossover and mutation in genetic algorithms" (PDF). IEEE Transactions on System, Man and Cybernetics. 24 (4): 656–667. doi:10.1109/21.286385.
  21. ^ Zhang, J.; Chung, H.; Lo, W. L. (2007). "Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms". IEEE Transactions on Evolutionary Computation. 11 (3): 326–335. doi:10.1109/TEVC.2006.880727. S2CID 2625150.
  22. ^ 예를 들어 Evolution-in-a-nutshell Archived in the Wayback Machine 2016년 4월 15일 또는 여행 세일즈맨 문제, 특히 에지 재조합 연산자의 사용 예를 참조하십시오.
  23. ^ Goldberg, D. E.; Korb, B.; Deb, K. (1989). "Messy Genetic Algorithms : Motivation Analysis, and First Results". Complex Systems. 5 (3): 493–530.
  24. ^ 유전자 발현:진화적 계산에서 누락된 연결
  25. ^ Harik, G. (1997). Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms (PhD). Dept. Computer Science, University of Michigan, Ann Arbour.
  26. ^ 토모이아거 B, 친드리쉬 M, 섬퍼 A, 수드리아-안드레우 A, 빌라필라-로블레스 R.NSGA-II. 에너지에 기반한 유전 알고리즘을 이용한 배전 시스템의 파레토 최적 재구성2013; 6(3):1439-1455.
  27. ^ Gross, Bill. "A solar energy system that tracks the sun". TED. Retrieved 20 November 2013.
  28. ^ Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF)
  29. ^ "Flexible Muscle-Based Locomotion for Bipedal Creatures".
  30. ^ Evans, B.; Walton, S.P. (December 2017). "Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation". Applied Mathematical Modelling. 52: 215–240. doi:10.1016/j.apm.2017.07.024. ISSN 0307-904X.
  31. ^ Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
  32. ^ Turing, Alan M. (October 1950). "Computing machinery and intelligence". Mind. LIX (238): 433–460. doi:10.1093/mind/LIX.236.433.
  33. ^ Barricelli, Nils Aall (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
  34. ^ Barricelli, Nils Aall (1957). "Symbiogenetic evolution processes realized by artificial methods". Methodos: 143–182.
  35. ^ Fraser, Alex (1957). "Simulation of genetic systems by automatic digital computers. I. Introduction". Aust. J. Biol. Sci. 10 (4): 484–491. doi:10.1071/BI9570484.
  36. ^ Fraser, Alex; Burnell, Donald (1970). Computer Models in Genetics. New York: McGraw-Hill. ISBN 978-0-07-021904-5.
  37. ^ Crosby, Jack L. (1973). Computer Simulation in Genetics. London: John Wiley & Sons. ISBN 978-0-471-18880-3.
  38. ^ 1996년 2월 27일 - UC버클리 대학의 한스 브레머만 명예교수이자 수리생물학의 선구자, 69세의 나이로 사망
  39. ^ Fogel, David B., ed. (1998). Evolutionary Computation: The Fossil Record. New York: IEEE Press. ISBN 978-0-7803-3481-6.
  40. ^ Barricelli, Nils Aall (1963). "Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life". Acta Biotheoretica. 16 (3–4): 99–126. doi:10.1007/BF01556602. S2CID 86717105.
  41. ^ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 978-3-7728-0373-4.
  42. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
  43. ^ Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. ISBN 978-3-7643-0876-6.
  44. ^ Schwefel, Hans-Paul (1981). Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. Chichester ; New York: Wiley. ISBN 978-0-471-09988-8.
  45. ^ Aldawoodi, Namir (2008). An Approach to Designing an Unmanned Helicopter Autopilot Using Genetic Algorithms and Simulated Annealing. p. 99. ISBN 978-0549773498 – via Google Books.
  46. ^ Markoff, John (29 August 1990). "What's the Best Answer? It's Survival of the Fittest". New York Times. Retrieved 13 July 2016.
  47. ^ 루지에로, 머레이 A..(2009년 8월 1일) Wayback Machine에서 15년 및 2016년 1월 30일 아카이브 완료.Futuresmag.com 를 참조해 주세요.2013-08-07에 취득.
  48. ^ Evolver: 스프레드시트를 위한 고도의 최적화.팰리세이드.2013-08-07에 취득.
  49. ^ 최적화 알고리즘 평가 및 MATLAB 파생상품 없는 Optimizer 벤치마킹을 위한 벤치마크 실무자 Rapid Access, IEEE Access, vol.7, 2019.
  50. ^ Cohoon, J; et al. (2002). Evolutionary algorithms for the physical design of VLSI circuits (PDF). Advances in Evolutionary Computing: Theory and Applications. Springer, pp. 683-712, 2003. ISBN 978-3-540-43330-9.
  51. ^ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1 January 1999). BOA: The Bayesian Optimization Algorithm. Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1. Gecco'99. pp. 525–532. ISBN 9781558606111.
  52. ^ Pelikan, Martin (2005). Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms (1st ed.). Berlin [u.a.]: Springer. ISBN 978-3-540-23774-7.
  53. ^ Thierens, Dirk (11 September 2010). "The Linkage Tree Genetic Algorithm". Parallel Problem Solving from Nature, PPSN XI. pp. 264–273. doi:10.1007/978-3-642-15844-5_27. ISBN 978-3-642-15843-8. {{cite book}}:누락 또는 비어 있음 title=(도움말)
  54. ^ Ferreira, C. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems" (PDF). Complex Systems, Vol. 13, issue 2: 87-129.
  55. ^ Falkenauer, Emanuel (1997). Genetic Algorithms and Grouping Problems. Chichester, England: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  56. ^ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1 October 2004). "Model-Based Search for Combinatorial Optimization: A Critical Survey". Annals of Operations Research. 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427. doi:10.1023/B:ANOR.0000039526.52305.af. ISSN 0254-5330. S2CID 63137.
  57. ^ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r(2005) 입자 군집 최적화와 유전자 알고리즘 비교
  58. ^ Baudry, Benoit; Franck Fleurey; Jean-Marc Jézéquel; Yves Le Traon (March–April 2005). "Automatic Test Case Optimization: A Bacteriologic Algorithm" (PDF). IEEE Software. 22 (2): 76–82. doi:10.1109/MS.2005.30. S2CID 3559602. Retrieved 9 August 2009.
  59. ^ Civicioglu, P. (2012). "Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm". Computers &Geosciences. 46: 229–247. Bibcode:2012CG.....46..229C. doi:10.1016/j.cageo.2011.12.011.
  60. ^ Kjellström, G. (December 1991). "On the Efficiency of Gaussian Adaptation". Journal of Optimization Theory and Applications. 71 (3): 589–597. doi:10.1007/BF00941405. S2CID 116847975.

참고 문헌

외부 링크

자원.

튜토리얼