유전자 알고리즘 소개-JS 튜토리얼-php.cn

An Introduction to Genetic Algorithms 유전자 알고리즘은 "적합한 생존", 염색체 교차 및 돌연변이와 같은 자연 진화 과정을 시뮬레이션하여 문제에 대한 최상의 솔루션을 찾는 프로그램입니다. 이 기사는 유전자 알고리즘의 작문 방법을 간단히 소개하고 자체 알고리즘을 작성할 때 고려해야 할 몇 가지 중요한 요소를 논의하며 유전자 알고리즘의 실제 적용에 대한 몇 가지 예를 제공합니다.

키 포인트

유전자 알고리즘은 "적합한 생존"과 같은 진화 과정을 시뮬레이션하고 선택, 크로스 오버 및 돌연변이와 같은 메커니즘을 사용하여 복잡한 문제에 대한 최적의 해결책을 찾습니다. 유전자 알고리즘에서, 잠재적 솔루션은 염색체로 표현되며, 그 적용 성은 재생산을 위해 선택 될 확률을 결정하는 체력 기능에 의해 평가된다. 크로스 오버 프로세스는 한 쌍의 부모 솔루션의 기능을 결합하여 새로운 자손을 만들고, 변형은 자손의 무작위 변화를 도입하여 유전 적 다양성을 유지하고 잠재적으로 새로운 솔루션을 발견 할 수 있습니다.

유전자 알고리즘은 크고 복잡한 솔루션 공간을 효과적으로 탐색 할 수 있기 때문에 전통적인 검색 및 최적화 방법에서 해결하기 어려운 문제에 매우 효과적입니다.

유전자 알고리즘의 실제 적용은 성능 특성이 향상된 안테나 설계에서부터 웹 디자인 최적화에 이르기까지 다양하며, 이는 실제 문제를 해결하는 데있어 다양한 기능과 힘을 보여줍니다.

균열 알 수없는 정보

시간은 2369 년이며 인간은 별의 바다에 퍼졌습니다. 당신은 바쁜 딥 스카이 스타베이스에 주둔하는 젊고 똑똑한 의사입니다. 당신이 도착한 직후, 기지의 가게 주인이 당신에게 관심을 갖게되었습니다. 그는 자신이 단순한 재단사라고 주장하지만 소문에 따르면 그는 특히 사악한 정권을 위해 일하는 비밀 요원이라고한다.

당신은 매주 점심을 먹기 시작하여 정치에서시에 이르기까지 주제를 논의합니다. 몇 달 후에도, 당신은 그가 낭만적 인 감정을 표현하는지 또는 비밀을 취하고 있는지 확실하지 않습니다 (확실히 비밀이 없습니다). 어쩌면 둘 다.

어느 날 점심 시간에 그는 당신에게 도전했습니다. "나는 당신에게 말할 메시지가 있습니다. 편지, 구두점 당신은 의료실의 사무실로 돌아와서 여전히 그가 말한 것에 대해 생각하고 있습니다. 갑자기, 이전에 근처 컴퓨터에서 실행했던 유전자 시퀀싱 시뮬레이션 실험이 아이디어를주었습니다. 당신은 암호 암호 해독 전문가가 아니지만 유전학에 대한 전문 지식을 사용하여 그의 정보를 해독 할 수 있습니다!

일부 이론

처음에 언급했듯이, 유전자 알고리즘은 진화를 유도하여 솔루션을 검색하는 작업을 사용하는 프로그램입니다. 많은 반복 후, 알고리즘은 가능한 솔루션 세트에서 최고의 후보자 (추측)를 선택하고, 재결합하며, 어떤 조합이 솔루션에 더 가깝게 만드는지 확인합니다. 가난한 후보자는 버릴 것입니다.

위의 장면에서 비밀 메시지의 모든 캐릭터는 A-Z, 공간 또는 기본 구두점 일 수 있습니다. 이것이 우리에게 다음과 같은 32 자 "알파벳"을 준다고 가정합니다. abcdefghijklmnopqrstuvwxyz-. 그것들은 맞습니다. 각 가능성을 확인하는 데 너무 오래 걸립니다. 대신, 유전자 알고리즘은 무작위로 12자를 선택하고 재단사/스파이에게 결과가 그의 정보에 얼마나 가까운 지 평가하도록 요청합니다. 점수로 인해 미래 후보자를 미세 조정할 수 있기 때문에 이것은 Brute Force 검색보다 효과적입니다. 피드백을 통해 우리는 각 추측의 체력을 측정 할 수 있으며 막 다른 골목에 시간을 낭비하지 않기를 바랍니다.

homlk? wsrzdj, bgk ka! qtpxc 및 xelpocv.xlf!. 첫 번째 후보는 248.2, 두 번째 후보는 632.5, 세 번째 후보는 219.5입니다. 점수가 계산되는 방식은 나중에 논의 할 상황에 따라 다르지만 이제는 후보와 목표 정보 사이의 편차를 기반으로한다고 가정 해 봅시다. 완벽한 점수는 0입니다 (즉, 편차 없음; 후보와 목표는 다음과 같습니다. 동일), 점수가 높을수록 편차가 더 커집니다. 248.2 및 219.5의 점수를 가진 추측은 635.5 점수의 추측보다 비밀 정보의 내용에 더 가깝습니다.

미래의 추측은 최고의 시도의 조합을 통해 이루어집니다. 후보자를 결합하는 방법에는 여러 가지가 있지만 이제는 간단한 크로스 오버 접근 방식을 고려합니다. 새로운 추측의 각 캐릭터에는 첫 번째 또는 두 번째 부모 후보로부터 50-50 확률이 복사됩니다. 우리가 Homlk? wsrzdj와 xelpocv.xlf!의 두 가지 추측을 취한다면, 우리의 자손 후보의 첫 번째 캐릭터는 H의 확률이 50%, x의 50% 확률, 두 번째 문자는 O 또는 E이며, 곧. 자손은 안녕하세요? W.Rld!. 크로스 오버에 의해 새로운 후보자를 생성하지만, 부모 후보의 가치 만 사용하는 경우 여러 반복에 문제가있을 수 있습니다 : 다양성 부족. 우리가 한 후보가 모든 A로 구성되고 다른 후보는 모든 B로 구성되면 크로스 오버에 의해 생성 된 자손은 A와 B로만 구성됩니다. 솔루션에 C가 포함 된 경우 불행한 일입니다. ^{솔루션의 범위를 좁히 면서이 위험을 완화하고 다양성을 유지하기 위해 약간의 변화를 일으킬 수 있습니다. 50-50 세분화를 직접 수행하는 대신 알파벳의 값을 대체 할 확률이 적습니다. 이 돌연변이를 통해 자손은 Hello World!.}

돌연변이는 물건을 신선하게 유지합니다! 기대에 따르면, 유전자 알고리즘은 많은 유전자 과학 어휘를 빌립니다. 그래서 우리가 더 논의하기 전에, 몇 가지 용어를 개선합시다 :

<:> 대립 유전자 : 유전자 알파벳의 구성원. 대립 유전자의 정의는 알고리즘에 따라 다릅니다. 예를 들어, 0과 1은 이진 데이터를 처리하는 데 사용되는 유전자 알고리즘의 대립 유전자 일 수 있으며 코드를 처리하는 데 사용되는 알고리즘은 기능 포인터 등을 사용할 수 있습니다. 비밀 정보 시나리오에서 대립 유전자는 알파벳의 문자, 공간 및 다양한 구두점 자국입니다.

~~염색체 : 주어진 대립 유전자 서열; 우리의 시나리오에서 Homlk? wsrzdj, xelpocv.xlf!~~

유전자 : 염색체의 특정 위치에서 대립 유전자. 염색체 HOMLK? WSRZDJ의 경우, 첫 번째 유전자는 H이고, 두 번째 유전자는 O이고, 세 번째 유전자는 M 등입니다.

인구 : 문제에 대한 해결책으로 제안 된 하나 이상의 후보 염색체의 수집.

세대 : 알고리즘 특정 반복 중 인구. 한 세대의 후보자는 차세대 집단을 생산하기위한 유전자를 제공합니다.

피트니스 : 후보자가 원하는 솔루션에 얼마나 가까운 지에 대한 척도. 적응성 염색체는 유전자를 미래 후보에게 전달할 가능성이 높지만 적응성 염색체는 덜 폐기 될 가능성이 높습니다.

선택 : 생식 후보를 선택하는 과정 (새로운 후보 염색체 생성에 사용) 및 다른 후보자를 버립니다. 약한 후보자를 선택하기위한 내성이 다른 다양한 선택 전략이 있습니다.

<:> 생식 : 하나 이상의 후보자의 유전자를 결합하여 새로운 후보자를 생산하는 과정. 기증자 염색체는 아버지라고하며, 생성 된 염색체를 자손이라고합니다.

돌연변이 : 여러 세대의 유전 적 다양성의 손실을 방지하기 위해 자손에 무작위로 비정상적인 유전자가 도입되었습니다.

코드를 보여주세요!

고급 개요와 용어 목록이 주어지면 현재 일부 코드를보고 싶은 유혹을받을 수 있습니다. 비밀 정보 문제를 해결하는 JavaScript 코드를 살펴 보겠습니다. 읽기 과정에서 나는 "보일러 플레이트 코드"로 간주 될 수있는 방법과 우리가 해결하려는 문제와 더 밀접한 관련이있는 방법에 대해 생각하도록 초대합니다.

우리는 먼저 후보자 데이터 객체를 정의하고 염색체를 체력 점수와 짝을 이루기 만하면됩니다. 편의를 위해 정적 분류 방법도 부착됩니다.

다음, 우리는 유전자 알고리즘 자체를 구현하는 유전자 학적 클래스가 있습니다.

생성자는 시뮬레이션에 필요한 다양한 매개 변수를 해결하는 객체를 사용합니다. 유전자 알파벳, 대상 메시지 및 시뮬레이션이 실행되는 제약 조건을 정의하는 기타 매개 변수를 지정하는 방법을 제공합니다. 위의 예에서, 우리는 세대당 100 명의 후보자 인구를 기대합니다. 이것으로부터, 40 개의 염색체만이 생식을 위해 선택 될 것이다. 우리는 돌연변이를 도입 할 가능성이 3%이며, 발생하면 최대 2 개의 유전자를 바꿀 것입니다. MaxGenerations 값은 1 백만 세대 후에 솔루션에 수렴하지 않으면 스크립트를 종료합니다.

알고리즘을 실행할 때 제공되는 인구, 선택 크기 및 최대 연령 수는 상당히 작다는 것을 언급 할 가치가 있습니다. 더 복잡한 문제는 더 큰 검색 공간이 필요할 수 있으며, 이로 인해 알고리즘의 메모리 사용량과 실행 시간이 증가합니다. 그러나 작은 변형 매개 변수를 사용하는 것이 좋습니다. 그들이 너무 커지면, 우리는 피트니스를 기반으로 번식 후보자의 혜택을 잃고 시뮬레이션은 무작위 검색이되기 시작합니다.

randomint (), init () 및 run ()과 같은 방법은 보일러 플레이트로 간주 될 수 있습니다. 그러나 보일러 플레이트가 있다고해서 시뮬레이션에 실질적인 영향을 미치지 않는다는 의미는 아닙니다. 예를 들어, 유전자 알고리즘은 무작위성을 많이 사용합니다. 내장 된 Math.random () 함수는 우리의 목적에 적합하지만 다른 문제의 경우보다 정확한 임의의 생성기가 필요합니다. crypto.getrandomValues ()는 더 강한 암호화 임의 값을 제공합니다.

성능도 고려 사항입니다. 이 기사에서 명확하고 이해하기 쉽지만 작업이 반복 될 것임을 기억하십시오. 루프에서 코드를 마이크로 최적화하고보다 효율적인 메모리 데이터 구조를 사용하며 코드를 구현 언어와 상관없이 함수/메소드로 분리하는 대신 코드를 인라인해야 할 수도 있습니다.

calcfitness (), select (), repored () 및 stop () 메소드의 구현은 해결하려는 문제에 따라 다릅니다.

comcfitness ()는 특정 예상 기준에 따라 염색체의 체력을 측정하는 값을 반환합니다. 우리의 경우 비밀 메시지와 얼마나 잘 일치하는지입니다. 체력의 계산은 거의 항상 상황에 따라 다릅니다. 예를 들어, 두 값 사이의 해밍 거리 또는 레빈 슈타인 거리를 계산하고 여러 측정을 결합 할 수도 있습니다. 궁극적으로 피트니스 함수는 부울 "적합"/"맞지 않는"것이 아니라 당면한 문제에 따라 유용한 측정을 반환하는 것이 중요합니다.

select () 메소드는 엘리트 선택 전략을 보여줍니다. 전체 인구에서 가장 적합한 후보만이 번식을 위해 선택됩니다. 앞에서 언급했듯이 토너먼트 선택과 같은 다른 전략이 있습니다.이 전략은 인구의 개별 후보자 세트에서 가장 적절한 후보자를 선택하고 Boltzmann 선택과 함께 후보자 압력 선택에 점점 더 큰 후보자를 부과합니다. 이러한 다른 방법의 목적은 염색체가 즉시 명백하지 않더라도 나중에 유익 할 수있는 유전자를 전달할 수있는 기회를 갖도록하는 것입니다. 이러한 예제 구현뿐만 아니라 이러한 선택 전략 및 기타 선택 전략에 대한 심층적 인 설명은 온라인에서 쉽게 찾을 수 있습니다.

다양한 선택 전략을 설명하는 An Introduction to Genetic Algorithms 유전자를 결합하는 많은 방법이 있습니다. 우리의 코드는 각 유전자가 부모 중에서 선택할 확률이 동일하게 균일 한 크로스 오버를 사용하여 자손을 만듭니다. 다른 전략은 한 부모의 유전자가 아닌 한 부모의 유전자를 향한 경향이있을 수 있습니다. 또 다른 인기있는 전략은 k- 포인트 교차로, 여기서 염색체는 k 포인트로 나뉘어 단편을 결합하여 자손을 생산합니다. 교차로는 고정되거나 무작위로 선택 될 수 있습니다. K- 포인트 교차 전략에 대한 설명 우리는 두 개의 부모 염색체에 국한되지 않습니다. 임의의 다각형을 그려서 이미지를 진화시키는 알고리즘을 고려하십시오. 이 경우 염색체는 이미지 데이터로 구현됩니다. 각 세대에서 가장 적합한 이미지는 모집단에서 부모로서 선택되며 모든 아동 후보자는 부모 사본에 자신의 다각형을 그려서 생성됩니다. 부모 염색체/이미지는 부모의 독특한 변형/그림입니다. 유전자 알고리즘의 실질적인 적용 유전자 알고리즘은 엔터테인먼트와 수익성 모두에 사용될 수 있습니다. 아마도 유전자 알고리즘의 실제 적용의 가장 인기있는 두 가지 예는 BoxCar 2D와 NASA에 의해 진화 된 X- 밴드 안테나 일 것입니다.

BoxCar 2D는 유전자 알고리즘을 사용하여 시뮬레이션 된 지형을 통해 이동할 수있는 최고의 "자동차"를 발전시키는 시뮬레이션입니다. 자동차는 8 개의 랜덤 벡터로 구성되며 휠을 랜덤 포인트에 연결합니다. 이 프로젝트의 웹 사이트는 BoxCar2d.com에서 찾을 수 있으며, About Page에 알고리즘을 간단히 소개하고 최고의 디자인 중 일부를 보여주는 순위 목록을 제공합니다. 불행히도, 사이트는 플래시를 사용하며 이제 많은 사람들이 접근 할 수 없을 수 있습니다.이 경우 호기심이 많은 경우 YouTube에서 다양한 화면 녹화를 찾을 수 있습니다. rednuht.org/genetic_cars_2에서 찾을 수있는 HTML5 기술을 사용하여 Rafael Matsunaga가 작성한 유사한 (우수한) 시뮬레이션을 확인할 수도 있습니다.

카테고리에서 최고의 진화 안테나 인 사진은 자동 안테나 디자인 용지에서 나온 것입니다.

An Introduction to Genetic Algorithms 1 세대와 9 세대에 가장 적합한 레이아웃 인 사진은 최적화 된 웹 사이트 디자인의 논문에서 나옵니다. 지금까지, 당신은 유전자 알고리즘이 무엇인지에 대한 기본적인 이해를 가져야하고 자신의 연구에서 직면 할 수있는 자원을 해석하기 위해 어휘에 익숙해야합니다. 그러나 이론과 용어를 이해하는 것은 절반에 불과합니다. 자신의 유전자 알고리즘을 작성하려는 경우 특정 문제를 이해해야합니다. 시작하기 전에 다음은 스스로에게 물어볼 중요한 질문이 있습니다.

염색체로서의 문제를 어떻게 표현합니까? 내 유효한 대립 유전자는 무엇입니까?

목표가 무엇인지 알고 있습니까? 즉, 내가 무엇을 찾고 있습니까? 피트니스가 특정 임계 값을 초과하는 특정 값 또는 솔루션입니까?

후보 체력을 어떻게 정량화합니까?

새로운 후보 솔루션을 생성하기 위해 후보자를 어떻게 결합하고 돌연변이합니까? An Introduction to Genetic Algorithms

나는 또한 프로그램이 자연에서 영감을 얻는 방법을 이해하는 데 도움이되기를 바랍니다. 포럼에서 자신의 생각을 자유롭게 공유하십시오.

유전자 알고리즘에 대한 질문

에 자주 묻습니다

유전자 알고리즘 (GA)이란 무엇입니까? 유전자 알고리즘은 자연 선택 과정에서 영감을 얻은 휴리스틱 검색 및 최적화 기술입니다. 시뮬레이션 진화의 원리를 통해 최적화 및 검색 문제에 대한 대략적인 솔루션을 찾는 데 사용됩니다.

유전자 알고리즘은 어떻게 작동합니까? 유전자 알고리즘은 연속 세대에 걸쳐 후보 솔루션의 개체군을 발전시켜 작동합니다. 이 과정에는 용액의 품질을 반복적으로 개선하기 위해 선택, 교차 (재조합), 돌연변이 및 인구의 개인 평가가 포함됩니다.

유전자 알고리즘은 어떤 유형의 문제에 적합합니까? 유전자 알고리즘은 널리 사용되며 스케줄링, 라우팅, 기계 학습 및 기능 최적화를 포함하여 다양한 최적화 및 검색 문제에 적용될 수 있습니다.

유전자 알고리즘의 매개 변수를 선택하는 방법은 무엇입니까? 모집단 크기, 변동성 및 크로스 오버 속도와 같은 매개 변수는 특정 문제 및 솔루션 공간의 특성에 따라 다릅니다. 실험 및 튜닝은 주어진 문제에 대한 최상의 매개 변수 값을 찾는 일반적인 관행입니다.

유전자 알고리즘에서 체력 기능의 역할은 무엇입니까? 피트니스 기능은 주어진 문제에서 개별 솔루션의 수행 방식을 정량화합니다. 선택 프로세스를 안내하고 최적화 목표에 긍정적으로 기여하는 솔루션을 용이하게합니다.

위 내용은 유전자 알고리즘 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!