AncomWiki

Neighborhood Preserving Codes for Assigning Point Labels: Applications to Stochastic Search

Properties1
description이 논문은 확률적 탐색 알고리즘(예: 유전 알고리즘, 시뮬레이티드 어닐링)의 성능을 높이기 위한 해공간 표현 방법을 제안합니다. 기존 Gray Code 가 순서형 데이터에 국한된 반면, 본 연구는 임의의 그래프에서 인접한 점들을 작은 해밍 거리(Hamming distance)로 라벨링하는 'Neighborhood Preserving Codes'를 소개합니다. 이는 고차원 Gray Code 의 근사형으로, 그래프 정점 선택,…

5 min read

Neighborhood Preserving Codes for Assigning Point Labels: Applications to Stochastic Search

Source

  • Evernote/IFTTT Feedly/Neighborhood Preserving Codes for Assigning Point Labels Applications to Stochastic Search.md

Summary

이 논문은 확률적 탐색 알고리즘(예: 유전 알고리즘, 시뮬레이티드 어닐링)의 성능을 높이기 위한 해공간 표현 방법을 제안합니다. 기존 Gray Code 가 순서형 데이터에 국한된 반면, 본 연구는 임의의 그래프에서 인접한 점들을 작은 해밍 거리(Hamming distance)로 라벨링하는 ‘Neighborhood Preserving Codes’를 소개합니다. 이는 고차원 Gray Code 의 근사형으로, 그래프 정점 선택, 배낭 문제, 이진 패킹, 머신러닝 프로토타입 선택 등 다양한 조합 최적화 문제에 적용 가능합니다.

Key Points

  • 확률적 탐색에서 해의 작은 변화가 해공간에서 인접한 탐색을 유도하는 것이 지역 최적화(local optimization)에 중요함
  • 기존 Gray Code 는 순서형/이산 실수 인코딩에 주로 사용됨
  • 임의의 그래프 구조에서 인접 노드 간 해밍 거리를 최소화하는 새로운 라벨링 방법 제안
  • 표준 Gray Code 는 본 방법의 부분집합(subset)으로 포함됨
  • 적용 분야: 그래프 정점 선택, 배낭 문제, 이진 패킹, ML 프로토타입 선택, 스케줄링 문제 등

그래프 뷰

백링크