講座題目：求解點(diǎn)分割問(wèn)題的混合局部擾動(dòng)算法和增強(qiáng)學(xué)習(xí)方法

報(bào)告人：   Una Benlic 助理研究員，英國(guó)斯特林大學(xué)

講座時(shí)間：2015年05月15日上午10點(diǎn)

講座地點(diǎn)：kaiyun開云官方網(wǎng)站犀浦校區(qū)kaiyun開云官方網(wǎng)站會(huì)議室X2511

內(nèi)容簡(jiǎn)介：點(diǎn)分割問(wèn)題是一個(gè)經(jīng)典的NP-hard問(wèn)題，有著廣泛的應(yīng)用。我們提出了一種改進(jìn)的局部擾動(dòng)算法用于解決點(diǎn)分割問(wèn)題，該算法基于增強(qiáng)學(xué)習(xí)理論，使用了一種新的參數(shù)控制機(jī)制。在每次擾動(dòng)過(guò)程中，該算法以獨(dú)立的方式來(lái)設(shè)置擾動(dòng)類型和相應(yīng)的步長(zhǎng)。大量算法實(shí)驗(yàn)結(jié)果表明，該算法在點(diǎn)分割問(wèn)題上取得了相當(dāng)不錯(cuò)的實(shí)驗(yàn)結(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.