惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

月光博客
月光博客
C
Check Point Blog
博客园 - 司徒正美
D
DataBreaches.Net
Stack Overflow Blog
Stack Overflow Blog
MyScale Blog
MyScale Blog
人人都是产品经理
人人都是产品经理
博客园 - 三生石上(FineUI控件)
S
SegmentFault 最新的问题
大猫的无限游戏
大猫的无限游戏
Last Week in AI
Last Week in AI
H
Hackread – Cybersecurity News, Data Breaches, AI and More
宝玉的分享
宝玉的分享
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
雷峰网
雷峰网
博客园 - 叶小钗
Apple Machine Learning Research
Apple Machine Learning Research
云风的 BLOG
云风的 BLOG
A
About on SuperTechFans
P
Proofpoint News Feed
The GitHub Blog
The GitHub Blog
爱范儿
爱范儿
N
Netflix TechBlog - Medium
WordPress大学
WordPress大学

cs.NE updates on arXiv.org

MPCS: Neuroplastic Continual Learning via Multi-Component Plasticity and Topology-Aware EWC Combining Trained Models in Reinforcement Learning Training Non-Differentiable Networks via Optimal Transport ShiftLIF: Efficient Multi-Level Spiking Neurons with Power-of-Two Quantization Probe-Geometry Alignment: Erasing the Cross-Sequence Memorization Signature Below Chance Benchmarking local Hebbian learning rules for memory storage and prototype extraction Robust volatility updates for Hierarchical Gaussian Filtering Spiking Sequence Machines and Transformers Affinity Is Not Enough: Recovering the Free Energy Principle in Mixture-of-Experts Scalable Learning in Structured Recurrent Spiking Neural Networks without Backpropagation Geometric and dynamical analysis of attractor boundaries and storage limits in kernel Hopfield networks Attractor FCM Physical Foundation Models: Fixed hardware implementations of large-scale neural networks When Does Structure Matter in Continual Learning? Dimensionality Controls When Modularity Shapes Representational Geometry Learning to Forget: Continual Learning with Adaptive Weight Decay Causal Learning with Neural Assemblies NORACL: Neurogenesis for Oracle-free Resource-Adaptive Continual Learning Text-Utilization for Encoder-dominated Speech Recognition Models EdgeSpike: Spiking Neural Networks for Low-Power Autonomous Sensing in Edge IoT Architectures EvoTSC: Evolving Feature Learning Models for Time Series Classification via Genetic Programming Analysis and Explainability of LLMs Via Evolutionary Methods Deployment-Aligned Low-Precision Neural Architecture Search for Spaceborne Edge AI SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs MAEO: Multiobjective Animorphic Ensemble Optimization for Scalable Large-scale Engineering Applications Necessary and sufficient conditions for universality of Kolmogorov-Arnold networks Learn&Drop: Fast Learning of CNNs based on Layer Dropping Architecture-Induced Recoverability Bias in Differentiable Symbolic Regression Collocation-based Robust Physics Informed Neural Networks for time-dependent simulations of pollution propagation under thermal inversion conditions on Spitsbergen Structure-Guided Diffusion Model for EEG-Based Visual Cognition Reconstruction
A Tight Runtime Analysis of the $(1+(λ, λ))$ Genetic Algo...
Benjamin Doerr, Carola Doerr · 2015-06-19 · via cs.NE updates on arXiv.org

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably is useful, the $(1+(λ, λ))$ Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel: TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a $O(\max\{n\log(n)/λ, λn\})$ bound was proven for any offspring population size $λ\in [1..n]$. We improve this work in several ways, leading to sharper bounds and a better understanding of how the use of crossover speeds up the runtime in this algorithm. We first improve the upper bound on the runtime to $O(\max\{n\log(n)/λ, nλ\log\log(λ)/\log(λ)\})$. This improvement is made possible from observing that in the parallel generation of $λ$ offspring via crossover (but not mutation), the best of these often is better than the expected value, and hence several fitness levels can be gained in one iteration. We then present the first lower bound for this problem. It matches our upper bound for all values of $λ$. This allows to determine the asymptotically optimal value for the population size. It is $λ= Θ(\sqrt{\log(n)\log\log(n)/\log\log\log(n)})$, which gives an optimization time of $Θ(n \sqrt{\log(n)\log\log\log(n)/\log\log(n)})$. Hence the improved runtime analysis gives a better runtime guarantee along with a better suggestion for the parameter $λ$. We finally give a tail bound for the upper tail of the runtime distribution, which shows that the actual runtime exceeds our runtime guarantee by a factor of $(1+δ)$ with probability $O((n/λ^2)^{-δ})$ only.