講座題目：求解點分割問題的混合局部擾動算法和增強學(xué)習(xí)方法
報告人： Una Benlic 助理研究員，英國斯特林大學(xué)
講座時間：2015年05月15日上午10點
講座地點：kaiyun開云官方網(wǎng)站犀浦校區(qū)kaiyun開云官方網(wǎng)站會議室X2511
內(nèi)容簡介：點分割問題是一個經(jīng)典的NP-hard問題，有著廣泛的應(yīng)用。我們提出了一種改進的局部擾動算法用于解決點分割問題，該算法基于增強學(xué)習(xí)理論，使用了一種新的參數(shù)控制機制。在每次擾動過程中，該算法以獨立的方式來設(shè)置擾動類型和相應(yīng)的步長。大量算法實驗結(jié)果表明，該算法在點分割問題上取得了相當(dāng)不錯的實驗結(jié)果。
Title: Hybrid Breakout Local Search and Reinforcement Learning Approach to the Vertex Separator Problem
Reporter: Una Benlic, University of Stirling
Abstract: The Vertex Separator Problem (VSP) is an NP-hard problem which arises from several important domains and applications. In this lecture, we present an improved Breakout Local Search for VSP (named BLS-RLE), which uses a new parameter control mechanism that draws upon ideas from reinforcement learning theory. For each perturbation phase, BLS-RLE determines, in an interdependent manner, the number and the type of perturbation moves. Extensive experimental evaluations and statistical comparisons on a wide range of benchmark instances show significant improvement in performance of the proposed algorithm over the existing BLS algorithm for VSP.
