关于大数混合基表示的算法与问题

本文基于求解ｎ个简单同余方程组的思想给出了一个求解同余方程组的算法，算法将花费３ｎ次模运算及ｎ次求逆元运算，优于牛顿迭代法。对大数的混合基表示提出了扩张问题与压缩问题，并证明了扩张问题与其求解问题是线性等价的，而压缩问题的难度小于扩张问题。     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

遗传程序设计中分布式染色体的一个应用

对一类遗传程序设计问题，提出了简单等长的分布式染色体，取代复杂变长的树结构染色体，使演化算子操作更方便，个体复杂度得到有效控制．用该染色体形式解决割草问题，分析了分布式染色体带来的一些性质，并给出了很好的计算结果．     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

COSEARCH: A Parallel Cooperative Metaheuristic

In order to design a well-balanced metaheuristic for robustness, we propose the COSEARCH approach which manages the cooperation of complementary heuristic methods via an adaptive memory which contains a history of the search already done. In this paper, we present the idiosyncrasies of the COSEARCH approach and its application for solving large scale instances of the quadratic assignment problem (QAP). We propose an original design of the adaptive memory in order to focus on high quality regions of the search and avoid attractive but deceptive areas. For the QAP, we have hybridized three heuristic agents of complementary behaviours: a Tabu Search is used as the main search algorithm, a Genetic Algorithm is in charge of the diversification and a Kick Operator is applied to intensify the search. The evaluations have been executed on large scale network of workstations via a parallel environment which supports fault tolerance and adaptive dynamic scheduling of tasks.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

Hereditary optimal control problems: Numerical method based upon a padé approximation

In this paper, we consider a particular approximation scheme which can be used to solve hereditary optimal control problems. These problems are characterized by variables with a time-delayed argumentx(t – ). In our approximation scheme, we first replace the variable with an augmented statey(t) x(t - ). The two-sided Laplace transform ofy(t) is a product of the Laplace transform ofx(t) and an exponential factor. This factor is approximated by a first-order Padé approximation, and a differential relation fory(t) can be found. The transformed problem, without any time-delayed argument, can then be solved using a gradient algorithm in the usual way. Four problems are solved to illustrate the validity and usefulness of this technique.This research was supported in part by the National Aeronautics and Space Administration under NASA Grant NCC-2-106.     

R.C.曲线交叉粱系双目标优化设计的研究

本文对R.C正交直线-曲线粱系进行双目标优化设计,取结构造价和钢筋用量两类指标构造目标函数,建立了此类结构的基于Pareto最优性准则的数学模型,并对“线性加权和算法”进行改进,由此求得的综合最优解与一般算法的解答基本重合,而迭代计算的工作量却显著减少。对数值计算结果进行分析、讨论,得出一些比单目标优化设计更有理论和实际意义的结论。     

遗传算法在构象搜寻中的应用

遗传算法是一种模仿自然进化进程的新颖的启发式优化方法。通过它，人们可以在计算机上对所需的各种问题实施进化操作，最终产生理想的结果。遗传算法现已被广泛于计算机辅助设计、工程设计、系统模拟等领域并取得了极大的成功。本文拟对遗传算法在对大、中、小分子的构象搜寻中的应用作一较全面的综述。