In this research, we propose a variant of the Particle Swarm Optimization (PSO) algorithm, namely hybrid learning PSO (HLPSO), for skin lesion segmentation and classification. HLPSO combines diverse search mechanisms including modified Firefly Algorithm (FA) operations, a new spiral research action, probability distributions, crossover, and mutation procedures to diversify and improve the original PSO algorithm. It is used in conjunction with the K-Means clustering algorithm to enhance lesion segmentation. Its cost function takes both intra-class and inter-class variations into account to increase scalability. Two lesion classification systems are formulated based on HLPSO. In the first system, HLPSO is used to devise evolving convolutional neural networks (CNN) with optimized topologies and hyper-parameters for lesion classification. In the second system, shape and colour features, as well as texture features extracted using the Kirsch operator and Shift Local Binary Patterns are used to produce an initial discriminative lesion representation. HLPSO is then used to identify the most significant components of each feature vector for ensemble lesion classification. Evaluated using several skin lesion data sets, both systems depict superior capabilities in lesion segmentation, deep CNN architecture generation, and discriminative feature selection for ensemble lesion classification, and outperform a number of advanced PSO and FA variants, classical search methods, as well as other related models on skin lesion classification significantly. HLPSO also yields better performances over other classical and advanced search methods in solving a number of benchmark tasks related to mathematical landscapes and those in the complex CEC 2014 test suite.