讲座题目：求解点分割问题的混合局部扰动算法和增强学习方法
报告人： Una Benlic 助理研究员，英国斯特林大学
讲座时间：2015年05月15日上午10点
讲座地点：金沙威尼斯欢乐娱人城犀浦校区金沙威尼斯欢乐娱人城会议室X2511
内容简介：点分割问题是一个经典的NP-hard问题，有着广泛的应用。我们提出了一种改进的局部扰动算法用于解决点分割问题，该算法基于增强学习理论，使用了一种新的参数控制机制。在每次扰动过程中，该算法以独立的方式来设置扰动类型和相应的步长。大量算法实验结果表明，该算法在点分割问题上取得了相当不错的实验结果。
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.
