arXiv:1805.01623

Recent Progress on Graph Partitioning Problems Using Evolutionary Computation

Hye-Jin Kim, Yong-Hyuk Kim

제출 2018-05-04

원문 초록

The graph partitioning problem (GPP) is a representative combinatorial optimization problem which is NP-hard. Currently, various approaches to solve GPP have been introduced. Among these, the GPP solution using evolutionary computation (EC) is an effective approach. There has not been any survey on the research applying EC to GPP since 2011. In this survey, we introduce various attempts to apply EC to GPP made in the recent seven years.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.13218v1cs.DS공통 태그 Combinatorial Optimization, graph partitioning

수요가 있는 그래프 분할: 일반화된 컨던턴스와 그 응용

Graph Partitioning with Demands: Generalized Conductance and its Applications

본 논문에서는 일반적인 수요 모델 하에서 다양한 그래프 분할 문제를 연구한다. 각 문제에서 용량 함수 $c\colon E\to \mathbb{N}$와 수요 함수 $w\colon V\times V\to \mathbb{N}$가 주어진 그래프 $G=(V,E,c,w)$가 주어진다. 우리의 주요 관심사는 컷 $(S, \bar{S})$를 찾아 다음 양을 최소화하는 문제이다. \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] 여기서 $c( S, \bar{S} )$는 $S$와 $S$의 여집합 $\bar{S}$ 사이의 간선 비용이며, $w( S, V )=w( S )+w( S, \bar{S} )$는 $S$ 내부의 내부 수요 $w( S )$와 $S$의 꼭짓점과 $\bar{S}$의 꼭짓점 사이의 수요 $w( S, \bar{S} )$의 합이다. $ψ_w( S )$를 컷 $(S, \bar{S})$의 \emph{generalized conductance}(일반화된 컨던턴스)라 하고, $ψ_w( S )$를 최소화하는 과제를 Generalized Conductance Problem(일반화된 컨던턴스 문제)라 부른다. 주요 기여는 이 목적함수에 대해 $\mathcal{O}(\log n)$-근사 보장을 갖는 알고리즘을 제시하는 것이다. 이 결과는 양방향 환원을 통해 달성된다. 먼저 잘 알려진 Generalized $k$-Multicut Problem으로 환원하고, 이어서 잘릴 수 있는 수요량에 대한 추가 상한 제약이 있는 고전 Sparsest-Cut Problem의 제약 변형으로 환원한다. 더 나아가, 위 절차가 수요가 있는 그래프 분할(Graph Partitioning with Demands)에 대해 $\mathcal{O}(\log n)$-이기준 근사를 얻는 데 사용될 수 있음을 보인다. 여기서 목표는 $G\setminus C$의 모든 연결 성분 $H$에 대해 $w( H )\leq ρ\cdot w( V )$를 만족하는 최소 비용의 간선 부분집합 $C$를 찾는 것이다. 이는 차례로 수요가 있는 계층적 클러스터링(Hierarchical Clustering with Demands)—그래프를 점점 더 세분화된 클러스터로 분할하는 컷의 계층을 찾는 문제—에 대한 $\mathcal{O}(\log n)$-근사를 제공한다. 곱셈형 수요 함수(multiplicative demand functions)의 경우 이러한 보장을 $\mathcal{O}(\sqrt{\log n})$로 개선하며, 트리(tree)의 경우 모든 목적함수에 대해 $\mathcal{O}(1)$-근사를 얻는다.

arXiv:2607.13054v1cs.RO공통 태그 Survey, Combinatorial Optimization

환경 모니터링에서 커버리지 극대화를 위한 자율 UAV 경로 계획: 체계적 문헌 고찰

Autonomous UAV Route Planning for Coverage Maximization in Environmental Monitoring: A Systematic Literature Review

무인항공기(UAV)를 활용한 환경 모니터링에는 에너지 한계, 운영 제약, 기하학적 복잡성을 다루면서 커버 영역을 극대화하는 경로 계획 방법이 필요하다. 본 논문은 커버리지 중심 환경 모니터링을 위한 자율 UAV 경로 계획에 관한 진행 중인 체계적 문헌 고찰(SLR)의 절차와 예비 결과를 보고한다. 이 고찰은 PRISMA 2020 프레임워크를 따르며, 2015년부터 2026년까지 발표된 연구를 Scopus와 Web of Science에서 검색한다. 절차는 경로 계획(path planning), 커버리지 경로 계획(coverage path planning), 정보 경로 계획(informative path planning)에 초점을 두며, 알고리즘 계열, 커버리지 및 에너지 지표, 장애물 처리, 기하학적 환경 표현, 환경 제약을 강조한다. 현재 단계에서 562건의 기록이 식별되었고, 161건의 중복이 제거되었으며, 401건의 고유 기록이 제목, 초록, 키워드로 스크리닝되었다. 이 중 247건이 전문(full-text) 적격성 평가를 위해 유지되었고(235건 적격, 12건 경계 기록은 전문 검토 중 해결 예정), 유지된 연구의 예비 분석은 커버리지 중심 공식화, 다중 UAV 협조, 에너지 인식 최적화에 대한 강한 집중을 시사하는 반면, 날씨, 불확실성, 장애물이 많은 환경을 명시적으로 다루는 연구는 상대적으로 적다. 유지된 연구의 대부분은 시뮬레이션 기반 검증에 의존하여 잠재적인 시뮬레이션-현실 간 격차를 부각시키며, 최근 출판물은 강화학습, 하이브리드 최적화, 기하학 인식 계획에 대한 관심 증가를 보여준다. 이러한 초기 결과는 활발하지만 분절된 연구 환경을 나타내며, 현실적인 환경 모니터링 임무를 위한 성숙한 기법과 미해결 공백을 식별하기 위한 구조화된 종합의 필요성을 뒷받침한다.

arXiv:2607.09025v1cs.NE공통 태그 Survey, Combinatorial Optimization

과학적 발견을 위한 진화적 지능: 진화 계산에서 누적적 발견 시스템으로

Evolutionary Intelligence for Scientific Discovery: From Evolutionary Computation to Cumulative Discovery Systems

인공지능(AI)은 과학적 발견의 방식을 과제 특화 워크플로에서 개방형 후보 공간에서 실험 및 인간 피드백을 통해 탐험(exploration)을 체계적으로 조직하는 자율 시스템으로 전환시키고 있다. 진화 계산(EC)은 피드백 기반 발견을 위한 계산적 기반을 제공하는데, 집단 기반 탐색이 누적된 증거를 통해 탐험을 유도하면서 다양한 과학적 후보군을 유지할 수 있기 때문이다. 그러나 EC는 주로 사전에 정의된 문제에 대한 후보 정제에 집중하는 반면, 누적적 발견에는 경험의 보존이 요구된다. 이 간극을 해소하기 위해, 본 리뷰는 과학적 발견을 위한 진화적 지능(EI)을 소개한다. EI는 진화 주기에 걸쳐 후보 정제와 경험 보존을 연결함으로써 지속적인 탐험을 유지하는 과학적 AI 시스템을 특징짓는다. 우리는 무엇이 진화하는지, 후보가 어떻게 변화하는지, 후보가 왜 선택되는지, 피드백이 어디에서 발생하는지, 그리고 진화가 언제 일어나는지를 묻는 5차원 분석 프레임워크를 제안한다. 이 프레임워크는 EI가 고립된 탐색 궤적을 누적적 과학적 통찰로 어떻게 변환하는지를 명확히 한다. 또한 구체적인 과학적 개체의 진화에서부터 자동화된 연구 워크플로 조율에 이르기까지 다양한 발견 방식에 걸쳐 이 패러다임을 실증한다. 마지막으로, 평가, 프로세스 추적 가능성, 공유 인프라에 관한 핵심 병목 지점을 식별하고, 과학적 발견에서 EC에서 EI로의 전환을 촉진하기 위한 구체적인 로드맵을 제시한다.

arXiv:2607.06935v1math.OC공통 태그 Survey, Combinatorial Optimization

강화학습의 수학적 방법론

Mathematical methods of reinforcement learning

강화학습(RL)은 확률론, 최적화, 작용소 이론의 도구들에 점점 더 깊이 기반을 두고 있다. 이 서베이는 현대 강화학습 알고리즘의 설계와 분석을 뒷받침하는 수학적 구조를 체계적으로 정리한다. 마르코프 결정 과정(MDP)과 벨만 작용소(Bellman operator)에서 출발하여, 수렴 보장과 수렴 속도를 이끌어 내는 수축 사상(contraction mapping), 단조성(monotonicity), 고정점 이론을 가치 반복(value iteration), 정책 반복(policy iteration), 시간차(temporal-difference) 방식에 걸쳐 강조한다. 이어서 최적화 관점을 전개하는데, 확률적 근사(stochastic approximation)와 마팅게일(martingale) 방법, 볼록 쌍대성(convex duality), 그리고 미러/근위(mirror/proximal) 방법과 정규화의 연결 관계를 다룬다. 함수 근사(function approximation)는 선형 및 비선형 설정 모두를 다루며, 안정화(stabilization), 오차 분해(error decomposition), 그리고 종속 데이터 및 혼합 과정에 대한 집중 부등식(concentration inequality)을 통한 샘플 복잡도(sample complexity)를 포함한다. 나아가 오프-정책 평가/학습, 제약 강화학습과 제약 MDP(CMDP)를 다룬다. 전반에 걸쳐 공통된 작용소 및 변분적 관점 하에 알고리즘 템플릿을 통합하고, 유한 샘플 경계와 점근적 결과를 함께 조명한다. 이 논문은 강화학습에 관심 있는 확률론, 최적화, 통계학 연구자들에게 통합된 수학적 진입점을 제공하고자 한다.

arXiv:2607.07762v1cs.LG공통 태그 Survey, Combinatorial Optimization

조합 최적화 관점에서 본 신뢰할 수 있는 머신러닝: 서베이 및 연구 전망

Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives

현대 머신러닝(ML)은 경험적 성능 지표만으로는 동작을 특성화하기 어려운 복잡한 모델에 점점 더 의존하고 있다. 예측, 생성, 의사결정을 포함한 광범위한 태스크에서 유사한 경험적 성능을 보이는 모델들도 투명성, 해석 가능성, 견고성(robustness), 공정성(fairness), 프라이버시, 그리고 인증 가능성(certifiability) 측면에서 현저히 다른 특성을 나타낼 수 있다. 본 서베이는 최적화 및 인증 지향적 추론이 이러한 차이를 분석하는 유용한 프레임워크를 제공할 수 있음을 강조하며, 모델 학습 및 선택부터 감사(auditing) 및 인증에 이르는 다양한 태스크를 지원한다. 우리는 조합 최적화(CO)와 신뢰할 수 있는 ML의 교차점에서 이루어진 최근 발전을 검토하고 종합한다. 이는 해석 가능한 모델 학습, 설명 생성(explanation generation), 견고성 분석, 공정성 감사, 모델 압축(model compression), 그리고 프라이버시 공격 및 보호를 포함하는 학습 및 사후 학습 태스크 모두를 다룬다. 이러한 분야 전반에서 CO 형식화(formulation)는 그래디언트 기반 방법 등 순수 휴리스틱 접근법에 비해 전역 보장(global guarantee), 형식적 인증서(formal certificate), 트레이드오프의 명시적 처리 등 추가적인 역량을 제공한다. 확장성은 여전히 중요한 과제로 남아 있지만, 솔버(solver)와 하이브리드 알고리즘의 지속적인 발전은 신뢰할 수 있는 ML 시스템의 설계 및 배포에서 CO의 역할이 점차 확대될 것임을 시사한다.

arXiv:2607.14821v2cs.CV공통 태그 Survey

모달 경계의 흐림: 단일 모달에서 다중 모달 인물 재식별(ReID)에 대한 통합 서벡

Blurring Modal Boundaries: A Unified Survey from Single- to Multi-Modal Person Re-ldentification

인물 재식별(ReID)은 지능형 감시 시스템의 핵심 구성 요소로, 분리된 카메라 네트워크 간 신원을 매칭하는 것을 목표로 한다. 전통적인 방법은 주로 단일 모달 RGB 영상에 의존하지만, 낮은 조도와 가림(occlusion)과 같은 환경적 도전 과제에 종종 제약을 받는다. 이러한 한계를 극복하기 위해 해당 분야는 교차 모달(cross-modal) 및 다중 모달(multi-modal) 패러다임으로 빠르게 발전하고 있다. 본 서벡은 이러한 전환에 대한 포괄적인 개요를 제시하며, 직접 가시성을 넘어 지각을 확장하는 신흥 비시선(NLOS, Non-Line-of-Sight) ReID를 포함하여 가시-적외선(VI-ReID), 텍스트-이미지(TI-ReID), 스케치 기반(Sketch-ReID) 등 주요 교차 모달 과제를 체계적으로 검토한다. 또한 3분광(tri-spectral) 및 다중 모달 융합 ReID를 살펴보고, 다양한 센서의 상보적 정보가 어떻게 견고성(robustness)을 향상시키는지 논의한다. 데이터셋, 과제, 방법론을 요약하는 것을 넘어, 모달리티 불변(modality-invariant) 특징을 효과적으로 포착하도록 설계된 가시-적외선 ReID용 트랜스포머 기반 기준선 프레임워크를 제안한다. 마지막으로, 현재 연구 환경을 바탕으로 향후 연구를 위한 여러 유망한 방향을 제시한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.