求解容量受限中心聚类问题的进化算法研究

来源 :重庆大学 | 被引量 : 0次 | 上传用户:l040685
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
膜计算是一种根据细胞生物特性和功能抽象出来的新的计算模型。其进化规则的执行具有极大的并行性和不确定性。在实际应用时,膜进化算法可以根据不同问题的特点有针对性的设计进化算子,有效地提高全局搜索能力。容量受限中心聚类问题(Capacitated Centered Clustering Problem,CCCP)旨在将多个有需求的点分配到各个中心,在满足点的需求的同时使得各点到中心的距离和最小。该问题在设施选址、供应链设计等方面有很多应用。该问题是NP难的,其中心坐标的频繁变动和解的多样性要求较高的计算能力。目前,求解CCCP的算法在求解效率和求解质量方面都不能适应大规模应用问题的需要,因此,研究更高性能的算法具有重要的实际意义和理论意义。本文对膜计算模型和CCCP进行了研究。首先,根据CCCP计算密集的特点和已有算法的利弊,提出了新的搜索算法,解决了目前局部搜索组件求解质量不高的问题。进一步,结合膜计算的并行性和不确定性特点,设计了对应的膜进化算法,提高了CCCP的求解效率。本文的主要工作如下:(1)基于A-BRKGA(Adoptive biased random-key genetic algorithm)进化框架,提出了迭代邻域局部搜索算法A-BRKGA_INLS(Adoptive biased random-key genetic algorithm with iterative neighborhood local search)。(2)基于膜进化算法框架MEAF(Membrane evolutionary algorithm framework)和算法A-BRKGA_INLS中的局部搜索组件INLS,提出了求解CCCP的膜进化算法MEA-CCCP(Membrane evolutionary algorithm for the Capacitated Centered Clustering Problem)。在MEA-CCCP中,设计了CCCP解的膜结构和对象表示,设计了五个独立的膜进化算子。(3)实现了以上两个算法,并基于CCCP基准数据集对两个算法分别进行实验分析。实验结果表明,A-BRKGA_INLS和MEA-CCCP分别能在72%(38/53)和51%(32/63)的实例上匹配或超越已知最优解。两个算法均有效的提升了求解质量。A-BRKGA_INLS具有较强的稳定性,MEA-CCCP缩短了平均求解时间。本文的研究工作基于现有的框架提出了解决CCCP的改进策略。其次,MEA-CCCP验证了膜进化算法求解CCCP的可行性和有效性,该尝试对相关领域的研究有着一定的参考价值。
其他文献
农业是保障我国国民经济稳定高速发展的基础产业,对人民生活安定、社会秩序稳定以及经济发展有着不可替代的重要性。我国农业仍面临着农业生产条件差、农业生产成本高、农业生产规模效应不足等问题,农业经济发展不平衡的情况在我国不同区域间依旧比较严重。农业政策对于农业经济发展有着指导性作用,其能够合理分配和利用资源,给农业营造良好的发展环境和氛围,对农业经济增长有着深刻的影响。但现有研究鲜从政策工具视角来分析农
学位
社区治理是社会治理的基础单元和关键环节,也是保障社会治理体系良性运行的核心组成部分。党对基层社会治理的领导,是中国特色社会主义制度的鲜明标志和独特优势,也是解决社区治理中居民原子化、利益群体冲突、治理资源匮乏等问题的现实需要。党的十八大以来,国家在政策和制度层面对基层党组织建设给予了高度重视和大力支持,全国各地以“党建引领”为基本途径,创新性探索基层社区治理的实践模式。本文在梳理国内外关于党建引领
学位
在“走出去”与“一带一路”倡议大背景下,中国企业对外投资规模不断扩大,但随着国内劳动力成本的攀升,中国企业劳务输出的低成本优势正在逐渐丧失。同时,东道国对外籍员工配额逐年收紧,跨文化问题逐渐凸显,在这样的大环境下,属地化管理逐渐受到重视。与国内劳务市场不同,许多国际工程所在国经济相对落后,劳动力素质普遍较中籍员工低,且由于语言文化差异,信息的传达、劳工的管理也显得困难重重。而这诸多的风险因素将直接
学位
近年来,我国矿产资源开发、基础设施和民生工程建设等大型工程项目正如火如荼的进行,层状岩体在这些工程开发建设中扮演着重要的角色。大量工程实践表明,岩体失稳、顶板坍塌、岩爆等工程灾害的发生与层状岩体拉伸力学特性和工程循环扰动荷载密切相关。为有效规避此类工程灾害发生,给工程设计优化提供理论参考,亟需开展循环扰动荷载下层状岩石拉伸力学特性的研究。本文以工程中常见的层状砂岩为研究对象,开展了常规加载和梯级循
学位
多传感器检测系统广泛应用于通信、雷达定位、地震勘测、声纳传播、医疗诊断、环境检测、食品质量监控等多个领域。传感器阵列是整个系统关键的组成部分。针对气味信息的检测,选择具有交叉敏感性和广谱响应特性的传感器组成传感器阵列,其与模式识别算法相结合形成仿生嗅觉系统,进而推进行业的智能化发展。由于待检样本往往结构/成分复杂,所以在构造传感器阵列之初,为了获得尽可能多的信息,而选择较多的传感器组成传感器阵列。
学位
房地产市场已经成为各国宏观经济的重要组成部分,对各国宏观经济的平稳运行和金融系统稳定有着重要影响,在国民经济中具有不可替代的地位。房地产价格和风险防控已经成为学术界和政策层关注的热点问题。当前,中国房地产市场整体价格飙涨、宏观调控“愈调愈涨”,区域分化等问题十分突出。全球房地产市场呈现异常繁荣、趋同上涨的走势,新兴经济体与发达经济体分化的倾向十分明显。现有研究对房地产市场运行影响因素的分析多涉及土
学位
产蛋后期蛋鸡的肠道衰老会降低其对钙的吸收能力,导致蛋壳质量下降,是影响蛋品质的重要因素之一。较差的蛋品质在鸡蛋的运输保存过程中会导致蛋的破损率提高,对经济效益造成负面影响。因此,从营养调控的角度提高肠道对钙的吸收利用对改善产蛋后期蛋品质具有积极的意义。酪蛋白磷酸肽(Casein Phosphopeptides,CPP)作为一种生物活性肽,在促进机体的钙(Ca)、铁(Fe)等矿物元素吸收方面具有良好
学位
近年来构建纳米结构的表面改性方法成为改善材料物理、化学性能的重要方式,然而表面改性引入的界面电荷效应成为限制材料发展的重要因素。高性能的绝缘材料及储能介质是先进电气设备及能源存储的基石和先导,表面改性调控界面电荷的目的主要是抑制或增加界面电荷产生,从而提升相应的材料性能。抑制界面电荷注入与积聚是介质绝缘性能调控的重要手段,而通过表面改性方法增加界面电荷是提高介质储能密度的重要方式。高效、简便的表面
学位
航空涡扇发动机是现代主流飞机的动力来源,风扇叶片作为涡扇发动机进气道一级叶片,提供全部外涵道推力。叶片加工精度与表面质量直接决定着航空发动机服役性能及寿命,是制造中的关键问题。与实心叶片相异,空心风扇叶片拥有中空瓦楞式内部结构和复杂后掠式外部叶型,制造工艺需要同时满足叶片外形及壁厚精度要求。目前,国内空心风扇叶片制造处于预研阶段,前端制造采用的超塑成形/扩散链接(SPF/DB)工艺容易导致叶片成形
学位
利用传感器阵列进行信源定位是阵列信号处理领域的一个重要分支。近年来,近场信源定位技术得到了迅速发展,广泛应用在雷达、水下声呐系统、车联网等领域中。当信源位于阵列的菲涅尔区域,也即近场区域时,入射信号到达接收阵列的波前为球面,所以近场信源定位算法能给出信源的角度和距离参数。近场信源定位可以用于二维平面定位,也可以用于三维立体定位。其中,近场三维信源定位能够给出位于三维立体空间中的信源的俯仰角、方位角
学位