This paper addresses the challenge of minimizing the number of sensors needed to detect available on-street parking spaces while maintaining high accuracy. By utilizing a natural-selection inspired genetic algorithm, we aim to optimize sensor deployment on moving vehicles, such as buses and taxis, to effectively monitor parking availability. Traditional fixed sensor systems are labor-intensive and vulnerable to environmental damage. Our approach leverages mobile sensors, which provide cost-effective and accurate parking information. The findings highlight the efficiency of the proposed genetic algorithm in solving complex optimization problems related to parking sensor allocation in urban environments.