유전자 알고리즘을 사용한 도트 시뮬레이션

유전자 알고리즘을 사용한 도트 시뮬레이션 - 1부

Barbara Streisand

풀어 주다： 2025-01-08 08:13:46

원래의

215명이 탐색했습니다.

이 블로그 게시물에서는 유전 알고리즘(GA)을 사용하여 장애물을 피하면서 대상을 향해 이동하는 도트를 시뮬레이션하는 매력적인 프로젝트에 대해 자세히 설명합니다. GA는 자연 선택을 모방하여 대상과의 근접성을 기반으로 점의 모집단을 반복적으로 개선합니다.

Dots Simulation using Genetic Algorithm - Part 1

유전자 알고리즘 구현:

GA는 다음 표준 단계를 따릅니다.

초기화: 초기 도트 집단을 무작위로 생성합니다.
평가: 피트니스 기능은 대상과의 거리를 기준으로 각 점의 성능을 평가합니다.
선정: 가장 적합한 점을 다음 세대의 부모로 선택합니다.
교배: 두 부모의 유전 정보(이동 방향)가 결합되어 자손이 생성됩니다. (참고: 이 프로젝트는 처음에는 단순성을 위해 복제를 사용합니다. 크로스오버는 나중에 추가될 예정입니다.)
돌연변이: 다양성을 유지하기 위해 자손의 이동 방향에 사소한 무작위 변화가 도입됩니다.
교체: 이전 세대가 자손으로 교체됩니다.
엘리트주의: 이전 세대의 최고 성능 도트가 다음 세대에도 보존됩니다.
반복: 지정된 세대 수에 대해 2~7단계를 반복합니다.

시뮬레이션 개요:

시뮬레이션은 빨간색 정사각형 목표에 도달하기 위해 진화하는 점 집단을 시각화합니다. 각 점의 움직임은 해당 "유전자"(이동 방향의 순서)에 의해 결정됩니다. 선택, 돌연변이 및 복제를 통해 개체군은 적응하여 검은색 직사각형 장애물을 피해 이동하면서 목표에 도달하는 능력을 향상시킵니다.

주요 시뮬레이션 구성 요소:

점: 이동 방향(염색체)과 대상 근접성을 기반으로 한 피트니스 점수를 가진 에이전트.
피트니스 기능: 대상까지의 거리를 기준으로 피트니스를 계산하여 더 짧은 경로에 보상합니다.
인구: 세대를 거쳐 진화하는 점들의 집합
유전 알고리즘: 적합한 개체를 선택하고 변이를 도입하여 진화 과정을 주도합니다.
장애물: 점의 탐색에 도전하는 검은색 직사각형.
목표: 점이 도달하는 빨간색 사각형 과녁

프로젝트 설정(Pygame이 포함된 Python):

이 프로젝트는 시각화를 위해 Pygame을 사용합니다. 주요 전역 변수는 시뮬레이션의 매개변수(인구 규모, 돌연변이율 등)를 제어합니다. Dot 클래스는 개별 점을 나타내며 위치, 움직임, 체력을 관리합니다.

초기 시뮬레이션(단일 점):

초기 코드는 단일 점이 화면 경계를 벗어날 때까지 무작위로 움직이는 단일 점을 시뮬레이션합니다. 이는 모집단과 GA를 도입하기 전의 기본 단계 역할을 합니다.

인구 시뮬레이션:

Population 클래스는 점 그룹을 관리합니다. update 메서드는 점을 이동하고 장애물과의 충돌을 확인합니다. 이제 시뮬레이션에 동시에 움직이는 여러 개의 점이 표시됩니다.

장애물과 목표 추가:

Obstacle 및 Goal 클래스는 각각 장애물과 대상을 나타내기 위해 도입되었습니다. 충돌 감지 기능이 구현되어 충돌 시 도트가 "죽게" 됩니다. 이제 시뮬레이션에는 빨간색 사각형 표적과 검은색 직사각형 장애물이 포함됩니다.

유전 알고리즘 구현(복제):

get_fitness 클래스의 Dot 메서드는 적합도를 계산합니다. Population 클래스는 선택, 복제(처음에는 교차 대신), 돌연변이 및 엘리트주의를 구현하는 generate_next_generation 및 select_best_dots 메서드를 얻습니다. 이제 시뮬레이션에서는 세대에 걸쳐 인구가 진화하는 모습을 보여줍니다.

향후 개선 사항:

향후 블로그 게시물에서 다룰 내용은 다음과 같습니다.