메모리 알고리즘

의 시리즈의 일부
진화 알고리즘
인공 개발 인공 생명 세포진화알고리즘 문화 알고리즘 미분 진화 효과적인 피트니스 진화 계산 진화 전략 가우스 적응 진화적 멀티모달 최적화 입자 군집 최적화 메모리 알고리즘 자연 진화 전략 신경진화 프로모터 기반 유전 알고리즘 나선 최적화 알고리즘 자체 수정 코드 다형 코드
유전 알고리즘
염색체 클론 선택 알고리즘 크로스오버 돌연변이 유전자 기억 유전적 퍼지 시스템 선택. 플라이 알고리즘
유전자 프로그래밍
데카르트 유전 프로그래밍 선형 유전 프로그래밍 문법적 진화 다중 표현식 프로그래밍 유전자 개량 스키마 유리스코 패리티 벤치마크
v t

컴퓨터 과학 및 운영 연구에서의 Memetic Algorithm(MA)은 전통적인 유전 알고리즘의 확장입니다.최적화 문제에 대한 충분한 해결책을 제공할 수 있습니다.로컬 검색 기술을 사용하여 조기 ^[1]수렴 가능성을 줄입니다.

밈 알고리즘은 진화 계산에서 최근 증가하고 있는 연구 영역 중 하나입니다.MA라는 용어는 현재 문제 검색을 위한 개별 학습 또는 국지적 개선 절차를 통해 진화적 또는 모집단 기반 접근법의 시너지 효과로 널리 사용되고 있다.문헌에서는 MA를 Baldwinian Evolutional Algorithm(EA; 볼드윈 진화 알고리즘), Lamarkrian EA, 문화 알고리즘 또는 유전자 로컬 검색이라고도 부릅니다.

서론

자연 진화의 모두 다윈의 원칙과 밈은의 도킨스의 개념에서 영감을 받아 이 용어는 밈 중심 알고리즘(MA)파블로 모스카토에 의해 그의 기술적 report[2]에 1989년 그가population-based 하이브리드 유전 알고리즘(GA)개인 학습 절차 수행할 수 있는과 더불어 한 형태로 문학 석사를 소개되었다.lo세세한 부분까지 조정한편으로 다윈의 진화, 다른 한편으로 밈과 도메인 고유(로컬 검색) 휴리스틱스 사이의 은유적 유사성은 밈 알고리즘 내에서 포착되어 일반성과 문제 특수성 사이에서 균형을 잘 잡는 방법론을 제시한다.이 2단계 성질은 그들을 2상 진화의 특별한 사례로 만든다.

좀 더 다양한 맥락에서, 밈 알고리즘은 이제 하이브리드 진화 알고리즘, 볼드윈 진화 알고리즘, 라마르크 진화 알고리즘, 문화 알고리즘 또는 유전자 로컬 검색을 포함한 다양한 이름으로 사용됩니다.복잡한 최적화의 맥락에서, 밈 알고리즘의 많은 다른 인스턴스화는 일반적으로 기존의 ^[3]진화적 알고리즘보다 더 효율적으로 고품질 솔루션으로 수렴되는 광범위한 애플리케이션 도메인에 걸쳐 보고되었다.

일반적으로 계산 프레임워크 내에서 밈학 개념을 사용하는 것을 밈 컴퓨팅 또는 밈 계산(MC)^[4][5]이라고 합니다. MC를 사용하면 보편적 다윈주의의 특성이 더 적절하게 포착됩니다.이러한 관점에서 보면, MA는 MC의 보다 제약적인 개념이다. 보다 구체적으로 MA는 MC의 한 영역을 다루고 있으며, 특히 최적화 문제를 해결하기 위해 다른 결정론적 정제 기법과 결합하는 진화 알고리즘의 영역을 다루고 있다.MC는 지식 강화 절차 또는 표현의 개념적 실체를 포함하도록 밈의 개념을 확장한다.

MA의 개발

제1세대

MA의 1세대는 하이브리드 알고리즘을 말합니다.혼합 알고리즘은 인구 기반 글로벌 검색(종종 진화 알고리즘의 형태로)과 문화적 진화 단계 간의 결합입니다.이 1세대 MA는 검색 사이클에서 문화적 진화(국지적 정제 형태)의 특성을 포함하지만, 상속/기억 전달, 변화 및 선택의 모든 핵심 원칙이 누락되었기 때문에 보편적 다윈주의에 따라 진정한 진화의 시스템으로 인정되지 않을 수 있다.왜 MA라는 용어를 처음 ^[2]도입했을 때 연구자들 사이에 비판과 논란을 불러일으켰는지 짐작할 수 있는 대목이다.

유사코드

절차 메모리 알고리즘 초기화:초기 모집단을 생성합니다. 정지 조건이 충족되지 않는 동안 모집단의 모든 개인을 평가하십시오.확률적 검색 연산자를 사용하여 새로운 모집단을 진화시킵니다.개개의 개선절차를 거쳐야 하는 개개의 $,$ ${\displaystyle {select}_{}}$ i l \ $Omega$_ {$il$} 를 선택합니다.${\displaystyle {\omega }_{}}$ i$$ \ $displaystyle \Omega$ _${il}$의 각 개인에 대해 f i ${\displaystyle l_{}}$ \$displaystyle f_{il$의 $빈도{\displaystyle {}_{}}$ 또는 확률을 가진 meme를 사용하여 t ${\displaystyle l_{}}$\ $displaystyle t_{il$의 기간 동안 개별 학습을 수행합니다. 라마르크식 또는 볼드윈식 학습을 진행합니다.동시에 끝나다

제2세대

Multi-meme,^[6] 하이퍼 휴리스틱^[7][8] 및 메타^[9] 라마르크식 MA를 2세대 MA라고 하며, 설계에서 밈 전송 및 선택 원리를 나타낸다.Multi-meme MA에서 밈 소재는 유전자형의 일부로 부호화된다.이어서 각 개인/염색체의 복호화된 밈을 사용하여 국소적인 미세화를 실시한다.그 후, 밈 물질은 부모로부터 자손에게 간단한 유전 메커니즘을 통해 전달된다.한편, 하이퍼 휴리스틱·메타 라마르크식 MA에서는, 지금까지의 보수 메카니즘에 의한 국지적인 개선의 메리트에 근거해, 검토된 후보 밈의 풀이 경쟁해, 장래의 국지적인 개선을 향해서 어떤 밈을 선택할지를 결정한다.보상이 높은 밈은 복제 또는 복사될 가능성이 높아집니다.2세대 MA, 즉 진화 시스템 내에서 여러 개별 학습 방법을 고려하는 MA에 대한 검토는 독자를 ^[10]참조한다.

제3세대

공진화^[11] 및 자가발전^[12] MA는 기본적인 진화 시스템의 정의를 충족하는 세 가지 원칙을 모두 고려한 3세대 MA로 간주할 수 있다.2세대 MA는 사용하는 밈이 선험적으로 알려져 있다고 가정하는 반면, 3세대 MA는 규칙 기반의 로컬 검색을 이용하여 진화 시스템 내에서 후보 해결책을 보완함으로써 문제 공간에서 정기적으로 반복되는 특징이나 패턴을 포착한다.

일부 설계 노트

이 섹션은 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 섹션 헤더를 질문으로 표현해서는 안 된다는 것입니다. 가능하다면 이 섹션의 개선에 협조해 주십시오.(2022년 6월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

개별 학습의 빈도와 강도는 주어진 제한된 계산 예산에 대해 MA 검색에서 개별 학습(활용)에 대한 진화(탐구)의 정도를 직접 정의한다.확실히, 보다 집중적인 개별 학습은 로컬 최적화에 대한 수렴 가능성을 높이지만, 과도한 계산 자원을 발생시키지 않고 확장될 수 있는 진화의 양을 제한한다.따라서 이 두 가지 매개변수를 설정할 때 검색 성능을 최대화하는 데 사용할 수 있는 계산 예산의 균형을 맞출 때 주의해야 한다.모집단의 일부만 학습을 받는 경우, MA 검색의 효용성을 극대화하기 위해 개선해야 할 개인의 하위 집합의 문제가 고려되어야 한다.마지막으로, 사용된 개별 학습 절차/밈은 또한 다른 인근 구조를 선호하기 때문에, 주어진 최적화 문제에 사용할 밈을 결정할 필요가 있다.

개인 학습은 얼마나 자주 적용되어야 하는가?

밈 알고리즘 설계와 관련된 첫 번째 문제 중 하나는 개별 학습의 적용 빈도, 즉 개별 학습 빈도를 고려하는 것이다.하나의 경우,^[13] MA 검색의 다른 단계에서 개별 학습 빈도의 다양한 구성이 조사된 경우, 개별 학습 빈도가 MA 검색 성능에 미치는 영향을 고려했다.반대로, 개인 학습의 계산 복잡도가 상대적으로 낮다면 모든 개인에게 개별 학습을 적용하는 것이 가치가 있을 수 있다는 것을 다른 곳에서 보여주었다^[14].

개별 학습을 사용해야 하는 솔루션은 무엇입니까?

각각의 학습,fitness-based과distribution-based 전략을 거쳐야 하는 EA사이에서 적절한 개인 선택 문제에 대해 염색체의 Land[15]와 계속적인 매개 변수 검색 문제의 인구는 꼭 온 것은 업무 확대에 개개인의 학습을 적용하는 확률을 위해 채택한 연구되었다.bina토리얼 최적화 문제밤바 외는 최대 솔루션 ^[16]품질을 달성하기 위해 매개 변수화된 개별 학습을 진화 알고리즘에 체계적으로 통합하기 위한 시뮬레이션 가열 기술을 도입했다.

개인 학습은 얼마 동안 진행해야 합니까?

개별 학습 강도$(\$는 개별 학습의 반복에 할당된 계산 예산(즉, 개별 학습이 단일 솔루션 개선에 지출할 수 있는 최대 계산 예산)입니다.

특정 문제나 개인에게 어떤 개별적인 학습 방법이나 밈이 사용되어야 하는가?

연속 최적화의 맥락에서 개별 학습은 국소 휴리스틱스 또는 기존의 정확한 열거 방법의 ^[17]형태로 존재한다.개별 학습 전략의 예로는 언덕 오르기, Simplex 방법, Newton/Quasi-Newton 방법, 내부 포인트 방법, 켤레 경사 방법, 선 탐색 및 기타 국소 휴리스틱이 있습니다.일반적인 개별 학습 방법의 대부분은 결정론적이라는 점에 유의하십시오.

반면 조합 최적화에서 개별 학습 방법은 일반적으로 특정 관심 문제에 맞춘 휴리스틱(결정론적 또는 확률론적)의 형태로 존재한다.대표적인 경험적 절차 및 방법에는 k-gene 교환, 에지 교환, 첫 번째 개선 등이 있습니다.

적용들

메메틱 알고리즘은 많은 실제 문제에 성공적으로 적용되어 왔습니다.많은 사람들이 밈 알고리즘과 밀접하게 관련된 기술을 사용하지만, 하이브리드 유전 알고리즘과 같은 대체 명칭도 사용된다.게다가, 많은 사람들은 그들의 밈 기술을 유전 ^{[citation needed]}알고리즘이라고 부른다.

연구자들은 많은 고전적인 NP 문제를 다루기 위해 밈 알고리즘을 사용해 왔다.예를 들어 그래프 분할, 다차원 배낭, 여행 세일즈맨 문제, 2차 할당 문제, 세트 커버 문제, 그래프 색칠 최소화, 최대 독립 집합 문제, 빈 패킹 문제, 일반 할당 문제 등을 들 수 있습니다.

보다 최근의 애플리케이션( 하지만 여기에만 국한되지 않는다)사업 분석과 데이터 인공 신경 networks,[18]패턴의 science,[3]훈련 recognition,[19]로봇 운동 planning,[20]빔 orientation,[21]회로 design,[22]전기 서비스 restoration,[23]의학 전문가 systems,[24]단일 기계 scheduling,[25]자동 timetabli을 포함한다.Ng(게 하고 인터넷은 시간표.NHL은 3),[26]인력 scheduling,[27]간호사 rostering optimisation,[28]프로세서 allocation,[29]정비 일정(전기 유통망, 예를 들어)[30]다차원 배낭 problem,[31일]하드웨어 고장 i.을 초고밀도 집적 회로 design,[32]유전자 표현의 클러스터링 profiles,[33]feature/gene selection,[34][35]매개 변수 결정njection,[36]과multi-class,multi-objecti기능 ^[37][38]선택

메모리 알고리즘의 최근 활동

• 메모리 알고리즘에 관한 IEEE 워크숍(WOMA 2009).프로그램 의장: 영국 웨스트오브잉글랜드 대학 짐 스미스, 싱가포르 난양공대 유순 옹, 영국 노팅엄대 구스타프슨 스티븐, 영국 난양공대 멍히오림, 싱가포르 나탈.
• Memetic Computing Journal은 2009년 1월에 창간되었습니다.
• 2008년 IEEE 컴퓨터 인텔리전스에 관한 세계 콩그레스(WCI 2008), 홍콩, 메모리 알고리즘에 관한 특별 세션.
• 소프트 컴퓨팅의 새로운 트렌드 - 메모틱 알고리즘에 관한 특별호, 소프트 컴퓨팅 저널, Completed & In Press, 2008.
• IEEE 컴퓨터 인텔리전스 소사이어티메트릭 컴퓨팅에 관한 이머징 테크놀로지
• IEEE 진화 계산 콩그레스(CEC 2007), 싱가포르, 메모리 알고리즘 특별 세션.
• Thomson Scientific의 필수 과학 지표가 제공하는 '메모리 컴퓨팅'이 새로운 전방 연구 분야로 부상하고 있습니다.
• 메모리 알고리즘, 시스템, 인간 및 사이버네틱스의 IEEE 트랜잭션에 관한 특별호 - Part B: Cybernetics, Vol. 37, No.1, 2007년 2월
• 메모리 알고리즘, 시리즈의 최근 발전:퍼지니스와 소프트 컴퓨팅에 관한 연구, 제166권, ISBN978-3-540-22904-9, 2005.
• 메모리 알고리즘에 관한 특집호, 2004년 가을, 제12권, 제3호: v-vi.

레퍼런스