改进遗传算法优化非线性规划问题

针对遗传算法在处理优化问题上的独特优势,主要研究遗传算法的改进,并将其应用于优化非线性规划问题.在进化策略上,采用群体精英保留方式,将适应度值低的个体进行变异;交叉算子采用按决策变量分段交叉方式,提高进化速度;在优化有约束非线性规划问题时,引入算子修正法,对非可行个体进行改善.MATLAB仿真实验表明,方法是一种有效的、可靠的、方便的方法.     

卫星舱内长方体群布局的优化模型及全局优化算法

本文研究了卫星舱内长方体群优化问题,建立了一个三维布局优化模型,并用图论,群论等工具克服了布局优化问题时断时续性质带来的困难,在此基础上构造了一个全局收敛的优化算法,文中所用的方法可用于求解类似问题。     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

二维混合布局问题的组合优化模型及算法

本文以卫星仪器舱布局优化设计问题为背景，分别以矩形和圆形为各种仪器的表征图元，建立二维混合布局的组合优化模型，并给出其主要性质和算法     

The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

混沌遗传算法对BP神经网络的改进研究

BP神经网络算法是目前应用最广泛的一种神经网络算法,但有收敛速度慢和易陷入局部极小值等缺陷.本文利用混沌遗传算法(CGA)具有混沌运动遍历性、遗传算法反演性的特性来改进BP神经网络算法.该算法的基本思想是用混沌遗传算法对BP神经网络算法的初始权值和初始阈值进行优化.把混沌变量加入遗传算法中,提高遗传算法的全局搜索能力和收敛速度;用混沌遗传算法优化后得到的最优解作为BP神经网络算法的初始权值和阈值.通过实验观察,改进后的结果与普通的BP神经网络算法的结果相比,具有更高的准确率.     

基于圆形件排样问题的遗传算法研究

排样性问题是一类优化求解问题,在遗传算法求解过程中,若所用的算法是不收敛的,则无法得到最优解.给出了一种混合式遗传算法,并证明了算法是完全收敛的,能够得到全局最优解.     

Relating Differential Distribution Tables to Other Properties of of Substitution Boxes

Due to the success of differential and linear attacks on a large number of encryption algorithms, it is important to investigate relationships among various cryptographic, including differential and linear, characteristics of an S-box (substitution box). After discussing a precise relationship among three tables, namely the difference, auto-correlation and correlation immunity distribution tables, of an S-box, we develop a number of results on various properties of S-boxes. More specifically, we show (1) close connections among three indicators of S-boxes, (2) a tight lower bound on the sum of elements in the leftmost column of its differential distribution table, (3) a non-trivial and tight lower bound on the differential uniformity of an S-box, and (4) two upper bounds on the nonlinearity of S-boxes (one for a general, not necessarily regular, S-box and the other for a regular S-box).     

An Algorithm to Compute Bounds for the Star Discrepancy

We propose an algorithm to compute upper and lower bounds for the star discrepancy of an arbitrary sequence of points in the s-dimensional unit cube. The method is based on a particular partition of the unit cube into subintervals and on a specialized procedure for orthogonal range counting. The cardinality of the partition depends on the dimension and on an accuracy parameter that has to be specified. We have implemented this method and here we present results of some computational experiments obtained with this implementation.     

工序质量管理方法的优化

本文简化了x-R控制图中各参数的估计;设计了直方图和工序能力指数动态应用工具。运用Excel软件使得计算便捷、界面直观、信息丰富。     

An Evolutionary Algorithm With Applications to Statistics

Evolutionary algorithms are used to find maxima of functions. Their claim to fame is an ability to find a global maximum in the presence of local maxima. The computations do not require derivatives or convexity, but still may be fairly computationally intensive in larger dimensions. This article presents a new type of evolutionary algorithm that works well in many dimensions, with the added advantage that linear equality constraints are implemented in a natural way. Bounds on the coordinates of the solution are also easy to implement. Several examples are presented and the new algorithm is compared with standard versions of evolutionary algorithms. The first group consists of functions in one or two dimensions, chosen to be difficult to maximize by gradient or simplex-based methods. The second set of examples are from statistics problems that are known to be computationally difficult. The first is least absolute deviations nonlinear regression with bootstrapped confidence bounds on the mean response, the second is smoothed nonparametric unimodal density estimation requiring both a linear equality constraint and linear inequality constraints. The Fortran subroutine is available for the user.     

An Efficient Algorithm to Identify DNA Motifs

We consider the problem of identifying motifs that abstracts the task of finding short conserved sites in genomic DNA. The planted (l, d)-motif problem, PMP, is the mathematical abstraction of this problem, which consists of finding a substring of length l that occurs in each s _i in a set of input sequences S = {s ₁, s ₂, . . . ,s _t } with at most d substitutions. Our propose algorithm combines the voting algorithm and pattern matching algorithm to find exact motifs. The combined algorithm is achieved by running the voting algorithm on t′ sequences, t′ < t. After that we use the pattern matching on the output of the voting algorithm and the reminder sequences, t ? t′. Two values of t′ are calculated. The first value of t′ makes the running time of our proposed algorithm less than the running time of voting algorithm. The second value of t′ makes the running time of our proposed algorithm is minimal. We show that our proposed algorithm is faster than the voting algorithm by testing both algorithms on simulated data from (9, d ≤ 2) to (19, d ≤ 7). Finally, we test the performance of the combined algorithm on realistic biological data.     

运用多目标规划优化功放的预失真模型

预失真技术是克服功率放大器非线性失真的一种非常有效的方法.许多研究者从数学建模的思想角度出发,建立了关于功放与预失真的各类级数模型,以实现线性增益输出.但是在应用通信系统中,这些模型不能有效地动态实现功放效率尽可能高的要求.在和记忆多项式模型的基础上,创新地运用多目标规划的方法优化功放的预失真模型.在满足一定的线性化输出的同时,尽可能地得到更高的功放效率,而且能同时计算出增益系数与模型参数.对于数据量为1000的无记忆功放得到增益倍数为1.82649,预失真模型的NMSE值为-41.5633.数据量为73920的有记忆功放得到增益倍数为9.5969,预失真模型的NMSE值为-24.3682.     

An Algorithm for the Fixed-Charge Assigning Users to Sources Problem

Given a set of sources with known capacities and a set of users with known demands for a product, the objective is to minimize the cost of assigning the users to the sources. The restrictions are that each user's demand is satisfied by exactly one of the sources, and that the total amount assigned to each source does not exceed its capacity. A fixed-charge version of this problem is formulated as a set partitioning problem and solved by a column-generating branch and bound procedure. Computational results are given.     

一种求解救灾物资运输问题的改进解法

本文通过对B运输问题建立数学模型,提出了一种求解B运输问题的改进解法。改进解法首先通过最小元素法求出初始解,然后进行变量闭回路法调整,直到求出最优解,并给出了一个计算实例证明了解法的有效性。文章还对改进解法和另外两种现有的算法进行了综合的分析,由于改进解法计算过程中采用的变量闭回路法省略了求检验数的环节,使得新算法比两种现有的算法更简便。     

基于遗传算法的快慢充充电站综合布局优化研究

随着能源和环境问题的日益加剧,电动汽车产业逐渐兴起.作为其运营所必须的基础配套服务设施,充电站的布局优化对于处在发展初期的电动汽车大规模推广应用具有重要意义.兼顾建设运营方和电动汽车用户方综合利益,以目标区域内建设快速充电站和慢速充电站综合费用最小化为目标,以满足电动汽车用户最大充电需求,保证用户充电便利性为约束条件,综合考虑地理位置、充电需求等因素建立了多等级电动汽车充电设施选址模型,并利用遗传算法求解模型.最后,算例表明所提出的方法和模型对目标区域电动汽车充电站的优化布局具有一定可行性和合理性.     

城市消防站点布局的改进启发式算法

面对数量较多需要及时处理的突发事故,为了满足最短应急时间限制,最低应急资源数和最少的出救点等目标,在城市规划决策中,考虑在一个确定应急限制期下的安全消防站选址问题,给出一个反映决策者对时间和费用偏好的折衷选址方案十分必要.从实际应用出发,运用改进启发式算法方法研究时间与资源限制条件下的多出救点组合模型求解问题.给出了应急限制期和安全消防设施点建立的费用模型,从理论上证明了模型求解方法的正确性.在给定限制期条件下,通过分析得出应急服务设施点选择方法.通过算例说明该计算方法的具体应用,为交通安全消防站点选择提供参考,该方法还适用于诸如医院急救站等类似公共设施的规划建设.     

一种改进的Snake算法

针对动态轮廓模型特性，本提出了一种能量函数的选取和收敛算法改进的新方法，结果表明，该方法在实际应用中效果理想。     

制造单元布局问题的双目标模型与算法研究

单元制造系统的布局对于提高系统的效率起着十分重要的作用。以最小化物料周转量和设施面积为目标,建立了一个单元制造系统布局的双目标优化模型,在该模型中不同制造单元的布局、单元内部不同设施的位置与方向这几个问题可以同时进行优化。基于模拟退火邻域解的变尺度生成机制和双目标抽样准则设计了模型的求解算法。算例表明本文算法所得Pareto解集优于经典的NSGA-Ⅱ算法。