检索结果-内蒙古大学图书馆

36th ACM International Conference on Supercomputing (ICS)

作者： Smith, Wesley Goldfarb, Aidan Ding, Chen Univ Rochester Rochester NY 14627 USA

ISBN: (纸本)9781450392815

Data movement is becoming the dominant contributor to the time and energy costs of computation across a wide range of application domains. However, time complexity is inadequate to analyze data movement. This work expands upon Data Movement Distance, a recently proposed framework for memory-aware algorithm analysis, by 1) demonstrating that its assumptions conform with microarchitectural trends, 2) applying it to four variants of matrix multiplication, and 3) showing it to be capable of asymptotically differentiating algorithms with the same time complexity but different memory behavior, as well as locality optimized vs. non-optimized versions of the same algorithm. In doing so, we attempt to bridge theory and practice by combining the operation count analysis used by asymptotic time complexity with peroperation data movement cost resulting from hierarchical memory structure. Additionally, this paper derives the first fully precise, fully analytical form of recursive matrix multiplication's miss ratio curve on LRU caching systems. Our results indicate that the Data Movement Distance framework is a powerful tool going forward for engineers and algorithm designers to understand the algorithmic implications of hierarchical memory.

关键词： matrix multiplication hierarchical memory algorithm analysis data movement

来源：评论

学校读者我要写书评

暂无评论

On time complexity analysis of algorithms

On time complexity analysis of algorithms

引用

9th World Multi-Conference on Systemics, Cybernetics and Informatics

作者： Tarek, Ahmed Eastern Kentucky Univ Dept Comp Sci Richmond KY 40475 USA

ISBN: (纸本)9789806560550

There exists a variety of techniques for the time complexity analysis of algorithms and functions. This analysis is used to find out the upper-bound on time complexity in big-oh notation, which is denoted by O(g(n)) with g(n) is a function of n, and n is the size of the given problem. Besides the big-oh complexity, there axe other complexity notations, such as Omega, theta, and small o complexities. Complexity analysis is used to select an appropriate algorithm for solving a given problem using computers. Unfortunately there does not exist any efficient, generalized framework for the time complexity analysis. Most of the existing techniques are complex, obsolete, and hard to use in practice. There is a misconception in some literature that 0(g(n)) is a function rather than a set. In this paper, it has been established that 0(g(n) is basically a set, which includes all algorithms with an upper bound on the order of g(n). Moreover, a generalized framework for analyzing the time-complexity function f (n) for algorithms in obtaining the big-oh notational complexity has been proposed. The method has been extended for functions f (n(1), n(2), ... , n(m)), m = 1, 2, ... involving multiple variables. Other complexity orders are discussed, and compared with the big-oh complexity.

关键词： time complexity complexity function big-oh notation complexity order algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Large Language Models for the Automated analysis of Optimization algorithms

Large Language Models for the Automated Analysis of Optimiza...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Chacon Sartori, Camilo Blum, Christian Ochoa, Gabriela Artificial Intelligence Res Inst IIIA CSIC Bellaterra Spain Univ Stirling Stirling Scotland

ISBN: (纸本)9798400704949

The ability of Large Language Models (LLMs) to generate high-quality text and code has fuelled their rise in popularity. In this paper, we aim to demonstrate the potential of LLMs within the realm of optimization algorithms by integrating them into STNWeb. This is a web-based tool for the generation of Search Trajectory Networks (STNs), which are visualizations of optimization algorithm behavior. Although visualizations produced by STNWeb can be very informative for algorithm designers, they often require a certain level of prior knowledge to be interpreted. In an attempt to bridge this knowledge gap, we have incorporated LLMs, specifically GPT-4, into STNWeb to produce extensive written reports, complemented by automatically generated plots, thereby enhancing the user experience and reducing the barriers to the adoption of this tool by the research community. Moreover, our approach can be expanded to other tools from the optimization community, showcasing the versatility and potential of LLMs in this field.

关键词： Optimization Large Language Models Prompt engineering algorithm analysis Operations Research Visualization Explainability

来源：评论

学校读者我要写书评

暂无评论

A study of drift analysis for estimating computation time of evolutionary algorithms

引用

Natural Computing 2004年第1期3卷 21-35页

作者： He, Jun Yao, Xin CERCIA School of Computer Science University of Birmingham Birmingham B15 2TT Edgbaston United Kingdom

This paper introduces drift analysis and its applications in estimating average computation time of evolutionary algorithms. Firstly, drift conditions for estimating upper and lower bounds of the mean first hitting times of evolutionary algorithms are presented. Then drift analysis is applied to two specific evolutionary algorithms and problems. Finally, a general classification of easy and hard problems for evolutionary algorithms is given based on the analysis. © 2004 Kluwer Academic Publishers.

关键词： algorithm analysis Combinatorial optimisation Evolutionary computation Meta-heuristics

来源：评论

学校读者我要写书评

暂无评论

Component-wise analysis of Automatically Designed Multiobjective algorithms on Constrained Problems

Component-wise Analysis of Automatically Designed Multiobjec...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Lavinas, Yuri Ladeira, Marcelo Ochoa, Gabriela Aranha, Claus Univ Tsukuba Tsukuba Ibaraki Japan Univ Brasilia Brasilia DF Brazil Univ Stirling Stirling Scotland

ISBN: (纸本)9781450392372

The performance of multiobjective algorithms varies across problems, making it hard to develop new algorithms or apply existing ones to new problems. To simplify the development and application of new multiobjective algorithms, there has been an increasing interest in their automatic design from component parts. These automatically designed metaheuristics can outperform their human-developed counterparts. However, it is still uncertain what are the most influential components leading to their performance improvement. This study introduces a new methodology to investigate the effects of the final configuration of an automatically designed algorithm. We apply this methodology to a well-performing Multiobjective Evolutionary algorithm Based on Decomposition (MOEA/D) designed by the irace package on nine constrained problems. We then contrast the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the hypervolume. Our results indicate that the most influential components were the restart and update strategies, with higher increments in performance and more distinct metric values. Also, their relative influence depends on the problem difficulty: not using the restart strategy was more influential in problems where MOEA/D performs better;while the update strategy was more influential in problems where MOEA/D performs the worst.

关键词： algorithm analysis continuous optimization automatic algorithm configuration multi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

AVERAGE-CASE analysis OF PERFECT SORTING BY REVERSALS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2011年第3期3卷 369-392页

作者： Bouvel, Mathilde Chauve, Cedric Mishna, Marni Rossin, Dominique Univ Bordeaux 1 CNRS LaBRI Bordeaux France Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Ecole Polytech CNRS LIX Palaiseau France

Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. Berard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals.

关键词： algorithm analysis genome rearrangements tree parameters simple permutations

来源：评论

学校读者我要写书评

暂无评论

Contributions to Convergence analysis of Noisy Optimization algorithms

Contributions to Convergence Analysis of Noisy Optimization ...

引用

作者： Mme. Sandra Astete-Morales UNIVERSITE PARIS SUD

学位级别：博士

This thesis shows several contributions to the convergence analysis for noisy optimization algorithms. We analyze the convergence rates for two algorithms of different type. One of the type linesearch and the other of the type Randomized Search Heuristics. We prove that the algorithm using an approximation of the Hessian matrix can reach the same rates as other optimal algorithms, when the parameters are well adjusted. Also, we analyze the convergence order for Evolution Stra- tegies for noisy optimization, using reevaluation. We obtain theoretical an empirical results for log- log convergence. We also prove a lower bound for the convergence rate of Evolution Strategies. We extend the work to the application of similar reeva- luation schemes to a discrete case presenting noisy perturbations in the objective function. Finally, we analyze the measure of performance itself by com- paring two quality indicator over different algo- rithms. We prove that the use of an inadequate indicator can lead to misleading results when com- paring several noisy optimization algorithms.

关键词： Optimization Noisy Optimization algorithm analysis Convergence of Optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

Evolutionary algorithm characterization in real parameter optimization problems

引用

APPLIED SOFT COMPUTING 2013年第4期13卷 1902-1921页

作者： Caamano, Pilar Bellas, Francisco Becerra, Jose A. Duro, Richard J. Univ A Coruna Integrated Grp Engn Res Ferrol 15403 Spain

This paper deals with the constant problem of establishing a usable and reliable evolutionary algorithm (EA) characterization procedure so that final users like engineers, mathematicians or physicists can have more specific information to choose the most suitable EA for a given problem. The practical goal behind this work is to provide insights into relevant features of fitness landscapes and their relationship to the performance of different algorithms. This should help users to minimize the typical initial stage in which they apply a well-known EA, or a modified version of it, to the functions they want to optimize without really taking into account its suitability to the particular features of the problem. This trial and error procedure is usually due to a lack of objective and detailed characterizations of the algorithms in the literature in terms of the types of functions or landscape characteristics they are well suited to handle and, more importantly, the types for which they are not appropriate. Specifically, the influence of separability and modality of the fitness landscapes on the behaviour of EAs is analysed in depth to conclude that the typical binary classification of the target functions into separable/non-separable and unimodal/multimodal is too general, and characterizing the EAs' response in these terms is misleading. Consequently, more detailed features of the fitness landscape in terms of separability and modality are proposed here and their relevance in the EAs' behaviour is shown through experimentation using standardized benchmark functions that are described using those features. Three different EAs, the genetic algorithm, the Covariance Matrix Adaptation Evolution Strategy and Differential Evolution, are evaluated over these benchmarks and their behaviour is explained in terms of the proposed features. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithm analysis Real parameter optimization Separability Modality

来源：评论

学校读者我要写书评

暂无评论

Characterization of Developmental Immature Fiber (im) Mutant and Texas Marker-I (TM-I) Cotton Fibers Using Attenuated Total Reflection Fourier Transform Infrared (ATR FT-IR) Spectroscopy

引用

APPLIED SPECTROSCOPY 2017年第7期71卷 1689-1695页

作者： Liu, Yongliang Kim, Hee-Jin ARS USDA Cotton Struct & Qual Res Unit SRRC New Orleans LA 70124 USA ARS USDA Cotton Fiber Biosci Res Unit SRRC New Orleans LA 70124 USA

The immature fiber (im) mutant is one type of cotton fiber mutant with unique characteristics of non-fluffy cotton bolls. Compared to its near-isogenic wild type Texas Marker-I (TM-I), im fiber has a thin secondary cell wall and is less mature. In this work, we applied the previously proposed principal component analysis (PCA) and simple algorithms to analyze the attenuated total reflection Fourier transform infrared (ATR FT-IR) spectra of developmental im and TM-I fibers. The results from these approaches could not effectively and consistently indicate the inherent difference between TM-I and im fibers at the same developmental stage. The difference between TM- I and corresponding im fibers was detected when comparing the normalized intensity variations of the 730 cm(-1) bands. The 730 cm(-1) band intensities in developmental im fibers are temporally lower than those in developmental TM-I fibers although they became similar when the TM-I and im fibers are fully mature. The observation might imply the likelihood of temporal reduction of amorphous regions in developmental im fibers rather than in developmental TM-I fibers.

关键词： Fourier transform infrared spectroscopy FT-IR attenuated total reflection ATR cellulose im mutant fiber secondary wall biosynthesis principal component analysis algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

UET SCHEDULING WITH UNIT INTERPROCESSOR COMMUNICATION DELAYS

引用

DISCRETE APPLIED MATHEMATICS 1987年第1期18卷 55-71页

作者： RAYWARDSMITH, VJ School of Information Systems University of East Anglia Norwich NR4 7TJ UK

We consider the problem of scheduling a partially ordered set of unit execution time (UET) tasks on m > 1 processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, ω c g satisfies w c g 3− 2 m w c opt − 1− 1 m where ω c opt is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behavour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.

关键词： UET scheduling list scheduling communication delays multiprocessor systems algorithm analysis NP-completeness speed-up anomaly

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：