진화 알고리즘

Evolutionary algorithm
의 시리즈의 일부
진화 알고리즘
유전 알고리즘
유전자 프로그래밍
시리즈의 일부
인공지능
Anatomy-1751201 1280.png
주요 목표
접근
철학
역사
테크놀로지
용어집

계산지능(CI)에서 진화알고리즘(EA)은 진화연산의 [1]서브셋으로 일반 모집단 기반의 메타휴리스틱 최적화 알고리즘이다.EA는 생식, 돌연변이, 재조합 및 선택과 같은 생물학적 진화에 영감을 받은 메커니즘을 사용합니다.최적화 문제에 대한 후보 솔루션은 모집단에서 개인의 역할을 하며, 적합성 함수는 솔루션의 품질을 결정합니다(손실 함수 참조).모집단의 진화는 위의 연산자를 반복적으로 적용한 후에 이루어진다.

진화 알고리즘은 모든 유형의 문제에 대한 근사적인 해결책을 잘 수행하는데, 이는 이상적으로 기초적인 적합성 환경에 대한 어떠한 가정도 하지 않기 때문이다.생물학적 진화의 모델링에 적용되는 진화 알고리즘의 기법은 일반적으로 세포 과정에 기초한 미세 진화 과정과 계획 모델의 탐구에 한정된다.대부분의 실제 EA 어플리케이션에서는 계산의 복잡성이 방해가 됩니다.[2]사실, 이러한 계산의 복잡성은 적합성 함수 평가 때문이다.피트니스 근사치는 이 어려움을 극복하기 위한 해결책 중 하나입니다.단, 단순해 보이는 EA는 복잡한 [citation needed]문제를 해결할 수 있습니다.따라서 알고리즘의 복잡성과 문제의 복잡성 사이에는 직접적인 연관성이 없을 수 있습니다.

실행

다음은 일반적인 단일 목적 유전 알고리즘의 예입니다.

1단계: 개인의 초기 모집단을 무작위로 생성한다(1세대).

2단계: 종료될 때까지 다음 재생 단계를 반복하십시오.

  1. 모집단 내 각 개인의 적합성 평가(시간 제한, 충분한 적합성 달성 등)
  2. 번식에 가장 적합한 개인을 선택하십시오. (부모)
  3. 교차 및 돌연변이 수술을 통해 새로운 개체를 번식시켜 자손을 낳습니다.
  4. 모집단에서 가장 적합도가 낮은 개인을 새 개인으로 바꿉니다.

종류들

유사한 기술은 유전적 표현과 기타 구현 세부사항, 그리고 적용된 특정 문제의 성격에서 다르다.

  • 유전 알고리즘– 가장 일반적인 유형의 EA입니다.재조합과 돌연변이와 같은 연산자(때로는 하나, 때로는 둘 다)를 적용하여 숫자의 문자열(전통적으로 2진수, 보통 가장 좋은 표현은 [2]해결되는 문제에 대한 무언가를 반영하는 표현이지만) 형태로 문제의 해결책을 모색한다.이런 유형의 EA는 최적화 문제에 자주 사용됩니다.
  • 유전자 프로그래밍 – 여기서 솔루션은 컴퓨터 프로그램의 형태로 되어 있으며, 그 적합성은 컴퓨터 문제를 해결하는 능력에 따라 결정됩니다.유전 프로그래밍에는 데카르트 유전 프로그래밍, 유전자 발현 프로그래밍, 문법 진화, 선형 유전 프로그래밍, 다중 표현 프로그래밍 등 많은 변형이 있습니다.
  • 진화적 프로그래밍 – 유전자 프로그래밍과 유사하지만 프로그램의 구조는 고정되어 있고 숫자 파라미터는 진화할 수 있습니다.
  • 진화 전략 – 솔루션의 표현으로서 실수의 벡터를 사용하여 동작합니다.일반적으로 자기 적응형 돌연변이율을 사용합니다.
  • 차분 진화 – 벡터 차이에 기반하므로 수치 최적화 문제에 주로 적합합니다.
  • 신경진화 – 유전자 프로그래밍과 비슷하지만 게놈은 구조와 연결 무게를 기술함으로써 인공 신경망을 나타냅니다.게놈 인코딩은 직접 또는 간접일 수 있습니다.
  • 학습 분류기 시스템 – 이 솔루션에서는 분류기 세트(규칙 또는 조건)가 있습니다.미시간-LCS는 개별 분류기 수준에서 진화하지만 피츠버그-LCS는 분류기 집합의 모집단을 사용한다.처음에는 분류자가 이진수였지만 이제는 실수, 신경망 또는 S-표현 유형을 포함합니다.적합성은 일반적으로 강도 또는 정확도 기반 강화 학습 또는 감독 학습 접근 방식으로 판단됩니다.

생물학적 과정과의 비교

많은 진화 알고리즘의 가능한[according to whom?] 한계는 유전자형-표현형 구분이 명확하지 않다는 것이다.자연에서, 수정란 세포는 성숙한 표현형이 되기 위해 배아 발생으로 알려진 복잡한 과정을 거친다.이러한 간접 부호화는 유전자 검색을 더욱 강력하게 하고(즉, 치명적인 돌연변이의 확률을 감소시키며)[3][4] 유기체의 진화 가능성을 향상시킬 수 있다고 믿어진다.이러한 간접적(생성적 또는 개발적) 인코딩은 환경에서의 [5]규칙성을 이용하기 위한 진화를 가능하게 합니다.인공배아학, 즉 인공발달시스템 분야의 최근 연구는 이러한 우려를 해결하고자 한다.그리고 유전자 발현 프로그래밍은 유전자형이 고정된 길이의 선형 다유전자 염색체로 구성되고 표현형은 크기와 모양이 [6][improper synthesis?]다른 여러 발현 나무 또는 컴퓨터 프로그램으로 구성되는 유전자형-표현형 시스템을 성공적으로 탐색합니다.

관련 기술

군집 알고리즘은[clarification needed] 다음과 같습니다.

  • 개미 군락 최적화는 페로몬 통신을 통해 개미에게 먹이를 찾아 경로를 [7]형성한다는 아이디어를 기반으로 합니다.주로 조합 최적화 및 그래프 문제에 적합합니다.
  • Runner-root algorithm(RRA; 러너 루트 알고리즘)은 자연 [8]속 식물의 주자와 뿌리의 기능에서 영감을 얻었다.
  • 인공 벌 군집 알고리즘은 꿀벌의 먹이찾기 행동을 기반으로 합니다.주로 수치 최적화를 위해 제안되며 조합, 제약 및 다목적 최적화 문제를 해결하기 위해 확장됩니다.
  • 벌 알고리즘은 꿀벌의 먹이찾기 행동을 기반으로 합니다.라우팅 및 스케줄링과 같은 많은 응용 프로그램에 적용되어 왔습니다.
  • 뻐꾸기 탐색은 뻐꾸기 종의 암매생에서 영감을 얻었다.또한 Levy 항공편을 이용하므로 글로벌 최적화 문제에 적합합니다.
  • 입자 군집 최적화는 동물 집단 [7]행동의 아이디어를 기반으로 한다.수치 최적화 문제에도 주로 적합합니다.

기타 모집단 기반 메타 휴리스틱 메서드

  • 사냥 검색 – 사냥감을 둘러싸기 위해 위치를 정리하는 늑대 등의 동물 집단 사냥에서 영감을 얻은 방법. 각 동물은 다른 동물과 특히 리더의 위치에 상대적입니다.조합 최적화 [10]방법으로 채택된 연속 최적화[9] 방법입니다.
  • 적응형 차원 검색 – 자연에서 영감을 받은 메타 휴리스틱 기법과 달리 적응형 차원 검색 알고리즘은 기본 원리로서의 은유를 구현하지 않습니다.대신 각 반복 [11]시 SDR(Search Dimensality Ratio) 매개 변수 업데이트를 기반으로 단순한 성능 지향 방법을 사용합니다.
  • 반딧불 알고리즘은 반딧불이의 행동에서 영감을 받아 섬광으로 서로를 끌어당깁니다.이는 멀티모달 최적화에 특히 유용합니다.
  • 하모니 검색 – 더 나은 하모니를 찾는 뮤지션의 행동에 대한 아이디어를 기반으로 합니다.이 알고리즘은 파라미터 최적화뿐만 아니라 조합 최적화에도 적합합니다.
  • 가우스 적응 – 정보 이론을 기반으로 합니다.제조 수율, 평균 적합성 또는 평균 정보의 최대화에 사용됩니다.예를 들어 열역학 및 정보 이론의 엔트로피를 참조하십시오.
  • Memetic Algorithm – Richard Dawkins의 밈 개념에서 영감을 얻은 하이브리드 방법으로서, 일반적으로 지역적인 개선을 수행할 수 있는 개별 학습 절차와 결합된 모집단 기반 알고리즘의 형태를 취합니다.문제별 지식 활용을 강조하고 로컬 및 글로벌 검색을 시너지 방식으로 조정하려고 합니다.

예

2020년에 구글은 AutoML-Zero가 신경망의 [12]개념과 같은 고전적인 알고리즘을 성공적으로 재발견할 수 있다고 발표했다.

컴퓨터 시뮬레이션 Tierra와 Avida는 거시 진화 역학을 모델링하려고 시도합니다.

갤러리

[13] [14] [15]

  • A two-population EA search over a constrained Rosenbrock function with bounded global optimum.

    구속된 로젠브로크 함수에 대한 2개의 모집단 EA 검색(유계 글로벌 최적).

  • A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.

    제약된 로젠브록 함수에 대한 2개의 모집단 EA 검색.전역 최적값이 경계가 없습니다.

  • Estimation of distribution algorithm over Keane's function

    킨 함수에 대한 분포 알고리즘 추정

  • A two-population EA search of a bounded optima of Simionescu's function.

    Simionescu 함수의 경계 최적화에 대한 2개의 모집단 EA 검색.

레퍼런스

  1. ^ Vikhar, P. A. (2016). "Evolutionary algorithms: A critical review and its future prospects". Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). Jalgaon: 261–265. doi:10.1109/ICGTSPICC.2016.7955308. ISBN 978-1-5090-0467-6. S2CID 22100336.
  2. ^ a b Cohoon, J; et al. (2002-11-26). 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.
  3. ^ G.S. 혼비와 J.B.명태."신체 뇌 진화를 위한 생성적 표현으로 높은 수준의 구성 요소 생성"인공생명, 8(3): 223~246, 2002.
  4. ^ 제프 클룬, 벤자민 베크만, 찰스 오브리아, 로버트 페녹."HyperNEAT Generative Encoding과 함께 진화하는 조정된 4단 Gaits" Wayback Machine에 2016-06-03 아카이브.IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009.노르웨이 트론하임
  5. ^ J. Clune, C. Ofria 및 R.PPSN(G. Rudolph, T. Jansen, S. M. Lucas, C)에서 T. Pennock은 "문제 규칙성이 감소함에 따라 생성 부호화가 어떻게 진행되는가"라고 말합니다.Poloni, and N. Beume, ed.) 컴퓨터 과학 강의 노트 제5199권, Springer, 2008. 페이지 358-367.
  6. ^ Ferreira, C., 2001."유전자 표현 프로그래밍: 문제 해결을 위한 새로운 적응 알고리즘"복잡한 시스템, 제13호, 제2호: 87~129.
  7. ^ a b Slowik, Adam; Kwasnicka, Halina (2018). "Nature Inspired Methods and Their Industry Applications—Swarm Intelligence Algorithms". IEEE Transactions on Industrial Informatics. Institute of Electrical and Electronics Engineers (IEEE). 14 (3): 1004–1015. doi:10.1109/tii.2017.2786782. ISSN 1551-3203. S2CID 3707290.
  8. ^ F. Merrikh-Bayat, "runner-root 알고리즘: 자연 속 식물의 뿌리와 러너에서 영감을 받은 단일 모드 및 다중 모달 최적화 문제를 해결하기 위한 메타 휴리스틱", Applied Soft Computing, Vol. 33, 페이지 292-303, 2015
  9. ^ Oftadeh, R.; Mahjoob, M.J.; Shariatpanahi, M. (October 2010). "A novel meta-heuristic optimization algorithm inspired by group hunting of animals: Hunting search". Computers & Mathematics with Applications. 60 (7): 2087–2098. doi:10.1016/j.camwa.2010.07.049.
  10. ^ Amine Agharghor; Mohammed Essaid Riffi (2017). "First Adaptation of Hunting Search Algorithm for the Quadratic Assignment Problem". Europe and MENA Cooperation Advances in Information and Communication Technologies. Advances in Intelligent Systems and Computing. 520: 263–267. doi:10.1007/978-3-319-46568-5_27. ISBN 978-3-319-46567-8.
  11. ^ Hasanchebi, O., Kazemzadeh Azad, S.(2015), "적응적 치수 검색: 이산 트러스 크기 최적화를 위한 새로운 메타휴리스틱 알고리즘", 컴퓨터 및 구조, 154, 1~16.
  12. ^ Gent, Edd (13 April 2020). "Artificial intelligence is evolving all by itself". Science AAAS. Archived from the original on 16 April 2020. Retrieved 16 April 2020.
  13. ^ Simionescu, P.A.; Beale, D.G.; Dozier, G.V. (2004). "Constrained optimization problem solving using estimation of distribution algorithms" (PDF). Proc. of the 2004 Congress on Evolutionary Computation - CEC2004. Portland, OR: 1647–1653. doi:10.1109/CEC.2006.1688506. S2CID 1717817. Retrieved 7 January 2017. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  14. ^ Simionescu, P.A.; Dozier, G.V.; Wainwright, R.L. (2006). "A Two-Population Evolutionary Algorithm for Constrained Optimization Problems" (PDF). 2006 IEEE International Conference on Evolutionary Computation. Proc 2006 IEEE International Conference on Evolutionary Computation. Vancouver, Canada. pp. 1647–1653. doi:10.1109/CEC.2006.1688506. ISBN 0-7803-9487-9. S2CID 1717817. Retrieved 7 January 2017.
  15. ^ Simionescu, P.A. (2014). Computer Aided Graphing and Simulation Tools for AutoCAD Users (1st ed.). Boca Raton, FL: CRC Press. ISBN 978-1-4822-5290-3.

외부 링크

참고 문헌